Building a Universal Turing Machine
Articles,  Blog

Building a Universal Turing Machine


Now we’re ready to describe
how to build this all powerful universal Turing machine. As input to the universal machine, we give the description of
the machine we want to simulate, and the input we want to simulate it on,
these two things separated by a #. The goal is to simulate m’s
execution when given the input w. That means we loop, accept, or
reject, just as M would on w. And if M does halt,
we want the universal machine to output the encoding of the tape
contents that M would have on w. We’ll describe as three
tape Turing machine. That achieves this goal
of simulating M on W. The input comes in on the first tape. And here I’ve just written out
the mathematical description. And first, we’ll copy this
description to the second tape. And we’ll put the initial
state on the third tape. For example, the tape contents
might end up like this. Then we rewind the heads and begin the second phase of actually
simulating the execution. Here we searched for the appropriate
tupal in the description of the machine. The first element has to match
the current state stored on tape three. And the symbol part has to
match the encoding on tape one. If no match is found,
then we just halt the simulation, and put the universal machine in
an accepting or rejecting state, according to the current state of
the machine being interpreted. If there is a match, however, then we
apply the changes to the first tape. Moving ahead to the right position and
so forth, and then repeat this process. So, actually, interpreting a Turing machine
description is surprisingly easy. We’ve just seen how Turing machines
are indeed reprogrammable, just like real world computers. This lends further support to
the Church Turing Thesis, but it also has a significance beyond that. Since the input to a Turing Machine can
be interpreted as a Turing Machine, this suggests that programs
are a type of data. But arbitrary data can also
be interpreted as a possibly invalid Turing Machine. So is there any difference
between data and program? I’ll leave this for you to discuss
with your friends over lunch or in the forums.

2 Comments

Leave a Reply

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