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.


Leave a Reply

Your email address will not be published. Required fields are marked *