[Solved]: How can a universal Turing machine simulate "bigger" ones?

Problem Detail: 

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?

Asked By : Panarit

Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41854