In his book The Emperor's New Mind, Roger Penrose gives an overview of Turing machines in Chapter 2. In his definition of what a Turing machine is he is very minimalist. There is a single linear tape infinite in both directions composed of cells, each of which is either blank or contains a single mark. He represents a blank as '0' and a mark as '1'. There is no separate blank ' ' space which the machine treats differently from '0'. (See page 37.)
Penrose walks through a scheme for encoding a Turing machine as a binary string of '0's and '1's. (See page 52.) He then introduces what a universal Turing machine $U(n,m)$ would do: simulate what the $n$th Turing machine $T_n$ would do with the input integer $m$. He says:
What the Turing machine $U$ would have to do, at each successive step of the operation of $T_n$ on $m$, would be to examine the structure of the succession of digits in the expression for $n$ so that the appropriate replacement in the digits for $m$ (i.e. $T_n$'s 'tape') can be made. In fact it is not difficult in principle (though decidedly tedious in practice) to see how one might actually construct such a machine. Its own list of instructions would simply be providing a means of reading the appropriate entry in that 'list' which is encoded in the number $n$, at each stage of application to the digits of the 'tape', as given by $m$. There would admittedly be a lot of dodging backwards and forwards between the digits of $m$ and those of $n$, and the procedure would tend to be exceedingly slow. Nevertheless, a list of instructions for such a machine can certainly be provided.
In the chapter's endnotes he gives a binary representation of a universal Turing machine he concocted, and which he says was verified by David Deutsch. He doesn't give any details about its implementation.
My question:
I would like to understand what he says is "not difficult in principle...to see". I'm having difficulty because of the restrictiveness of the binary alphabet. Other descriptions of universal Turing machines I've seen online use a more expansive alphabet, so that the machine can use a special character to mark where it needs to return when it is has completed doing something else. How would a Turing machine which only uses '0's and '1's for both input and output do its bookkeeping?
The input tape consists of
- the binary integer $n$
- followed by '111110' (which, because of the encoding Penrose has chosen, doesn't appear in any Turing machine $T_n$ which is correctly specified---see page 54) marking the end of the specification of $T_n$
- followed by the binary integer $m$ (and an extra '1', see bottom of page 54/top of page 55).
What if $T_n$ needs to write to the left of $m$? It can't overwrite the specification of $T_n$ itself, so it would need to copy the specification, shifting it to the left to make more blanks available. (Alternatively it could copy everything to the right of the specification for $T_n$ even further right.) I can't even see how $U$ would bookkeep a copy operation.
How could $U$ keep track of the current state that $T_n$ is in? When it is parsing $T_n$ to figure out what action it is next supposed to take, how could it keep track of where in $m$ it is supposed to go back to perform the action? Etc.
I'm not looking for anything too detailed, just something that would help me understand "in principle", as Penrose says. I suppose I could "disassemble" the universal Turing machine Penrose gives to see how he did it, but the binary specification is almost two pages of '0's and '1's and I'm not very excited about the prospect of doing that.