[Overview] [Previous] [Next]

Universal Turing Machines I

A computer, like an automaton, is necessarily hard-wired to execute a single algorithm. For a general-purpose stored-program computer, that algorithm is basically "fetch an instruction from the current location; execute the instruction; go to a new location." We can pull the same trick with a Turing machine: we will write a "program" directly on the tape, along with the "input" to that program. Then we will design a hard-wired universal Turing machine to emulate the Turing machine described on the tape.

We will store the program as a sequence of 5-tuples: (old state, symbol read, symbol to write, direction, new state).

We want our universal Turing machine to emulate any other Turing machine, even one with a larger tape alphabet. Hence, we will have to map the emulated alphabet into our own alphabet. The simplest way to do this is with a unary encoding, e.g. a₁=1, a₂=11, a₃=111, and so on. we can use a second tape symbol, say "0", to separate the symbols of the emulated alphabet.

Alternatively, we could use a binary notation, e.g. a₁=1, a₂=10, a₃=11, and so on. We would use some other symbol, say "x", to separate the characters. Many other encoding schemes are possible.

Similarly, we can use strings of digits to encode states, and to encode directions (L and R).

For example, to encode the 5-tuple

(q₁, a₂, a₅, L, q₃) in unary, we could use ...010110111110101110... This same 5-tuple could be encoded in binary as ...x1x10x101x1x11x...