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}=1, a_{2}=11, a_{3}=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}=1, a_{2}=10, a_{3}=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

Copyright © 1996 by David Matuszek

Last modified Mar 27, 1996