Before we can simulate a Turing machine, we first have to represent

it using a string. Notice that this represents

an immediate challenge. Our universal Turing machine must use

a fixed alphabet for its input and have a fixed number of states. But it must be able to simulate Turing

machines with arbitrarily larger alphabets and

an arbitrary number of states. As we’ll see, one solutions is

essentially to enumerate all the symbols and states and represent them in binary. There are lots of ways to do this. The way we’re going to do it,

is a compromise of readability and efficiency. So we’ll let M be a turning machine

with states q0 through qn- 1. And we’ll let it’s tape alphabet

be gamma a1 through am. We’ll define i and j so that 2 to the i

is at least the number of states. And 2 to the j is at least

the size of the tape alphabet. Then we can encode a state

qk as the string qw, where w is the binary

representation of k. For example,

if the number of states is 6, then we would need i to be 3, and so

we would encode q3 as the string q, and then 3 written out in binary, 011. By the way, we’ll use

the convention that q followed by the binary representation

of 0 is the initial state. q followed by the binary representation

of 1 is the accept state, and q followed by the binary representation

of 2 Is the reject state. We encode symbols much in the same

way as we encoded states. We’ll use a followed by w,

where w is the binary representation of this k to indicate the kth symbol. For example, if there are 10 different symbols, then

we need 4 bits to represent them all. And we might encode a5,

which could be any symbol. Maybe it’s a star. We would encode that as the string, a, followed by the binary

representation of 5, 4 plus 1 is 5. Let’s see an encoding for an example. This example decides whether the input

consists of a number of zeros, that is a power of two. To encode the Turing machine as a whole, we really just need to encode

the transition function. We’ll start by considering

this edge here. We’re going from state 0, so

I’ll write that this way. We see the symbol 0, so I’ll write

the encoding for that like so. And then we’re to state 3,

so i’ll write out that here. And then we need to write the $, so i’ll write out the encoding for

that, like so. And we’re supposed to move to the right. So I’ll write the R there. Remember that the order is input state, input symbol, output state,

output symbol, and then direction. Next, let’s do this

blue transition here. We go from state 3, and we read a 0. So I encode that that way. And then we’re going to state 4. So, I’ll write the encoding for

that with q, followed by the binary

representation of 4. And we’re supposed to write x. So I look up the encoding for

x, that’s a10, like so. And we want to move

the head to the right. So I include an R here. So that’s the convention we’ll use to

write out the transition function. It’s just a sequence of these

five tuples of this form, input state, input symbol, output state,

output symbol and then direction.