# How can a universal Turing machine simulate "bigger" ones?

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?

• 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.
– vzn
Commented Apr 28, 2015 at 18:07
• 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 Commented Apr 30, 2015 at 5:18

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.