10
$\begingroup$

I'm trying to find the answers of two questions about the Universal Turing machine.

  1. How can the Universal Turing machine simulate a Turing machine if the one that is being simulated has a bigger number of states?
  2. How can the Universal Turing machine simulate a Turing machine if the one that is being simulated has a bigger number of alphabet characters?

Can anyone help me with these questions?

$\endgroup$
  • 1
    $\begingroup$ another interesting pov wrt this is that the UTM can be built with a constant # of states. it simulates other TMs with arbitrary # of states or symbols encoded on the tape. $\endgroup$ – vzn Apr 28 '15 at 18:07
  • $\begingroup$ a related question is how can a TM simulate an ATM (alternating TM), which is roughly by same method pf encoding extra adata on tape plus a reduction of states into classes $\endgroup$ – Nikos M. Apr 30 '15 at 5:18
10
$\begingroup$

The answer to both subquestions is the same: by using the tape to store the necessary data. We can assume that the state set and alphabet of the machine to be simulated are subsets of the natural numbers ("State 1", "State 2", "State 3", etc.). Even with just two non-blank characters, the universal machine can represent all those integers as binary strings.

Note, though, that the universal machine has a fixed number of states, which makes computing the transition function a little tricky. What we'd like to do is write some instructions that implement a big switch statement of the form, "If the state is $s$ and the character under the head is $x$, then move to state $s'$, write character $x'$ and move the head in direction $d$." So – and I think this may be the root of your question – how do we calculate the transition function if we don't even have enough states in the universal machine to store the transition function's input?

One way is to store the transition function as a binary tree. Suppose all the simulated machine has $2^q$ states and $2^\ell$ tape symbols. Store the transition function as a binary tree of depth $q+\ell$ where, at the first $q$ levels, you go left or right according to whether the next bit of the simulated state is a one or a zero and the next $\ell$ levels are the same but for the successive bits of the simulated tape character. Now, your universal machine can walk backwards and forwards on its tape, checking the next bit of the state/character, remembering that bit in its own states, moving back to the tree, putting a marker at the correct node, and so on.

This gets somewhat easier if you let your universal machine have multiple tapes but then you still have to show that your multitape machine is equivalent to a single tape machine.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.