#### jbriggs444

Science Advisor

- 6,968

- 2,289

Early in a course in the Theory of Computing, one would encounter a number of basic proofs of equivalenceWe could, but we don't need to. Any positive number, or for that matter, any negative number or floating point number can be represented by a string of 0s or 1s. At heart, any data in a computer is composed of binary strings.

^{(*)}. Among these are proofs that Turing Machines running on a binary alphabet have power equivalent to Turing Machines running on arbitrary alphabet sizes. Or with an arbitrary number of tapes. Or with one way unbounded tape, etc. Or that an arbitrary TM can be simulated by a fixed finite Universal Turing Machine that is provided with a description of an emulated TM on input tape.

(*) Equivalent in the sense that if there is a TM of the one sort that can solve a given problem, there is also a TM of the other sort that can also do so.