1
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

One can overcome the limitations of binary characters by adding new states and treating binary characters as bounded-size groups – rather similarly to how physical computers combine zeroes and ones into bytes, words and beyond.

Suppose you have "all the symbols you'll need" in your alphabet, to implement a Turing machine you want. Let $N$ be the number of states – therefore you need $\lceil \log_2N \rceil$ bits to differentiate them. Let's call this number $b$.

A naïve but easy solution to convert the TM to binary is to assign each non-blank symbol a distinct combination of $b$ bits. When the original TM would move the head, we instead move $b$ times, and read the symbol represented by the bits by storing the bits read in the TM's state. This is possible, since $b$ is a constant affected only by the size of the original TM's alphabet. Writing a new symbol is likewise just a state transition to a chain of states which remembers the $b$ bits that need to be written and the state to proceed to from there.

All in all, this causes the TM to require a dramatic increase in the number of states, but the important point is not that it is efficient or easy but that it is possible.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Yes, I thought of this too, but it seemed to me that to get off the ground with this method $U$ would have to do an initial conversion of the tape, say, replacing each '0' by '00' and each '1' by '01', making room for '10' and '11' which would encode new symbols, say $a$ and $b$. To do this conversion, it seemed to me that $U$ would have to do some copying and shifting around, which are some of the actions I am struggling to see how it can do. $\endgroup$
    – frakbak
    May 31, 2022 at 16:21
  • $\begingroup$ @frakbak does it have to be about Penrose's specific machine, or just any machine with a binary alphabet? $\endgroup$
    – user253751
    Jun 2, 2022 at 15:59
  • $\begingroup$ @user253751 It doesn't need to be about Penrose's specific machine. I would just like to understand how a universal Turing machine which reads and writes only '0's and '1's can do basic things like copying and moving sections of the tape around, keep track of state, etc. $\endgroup$
    – frakbak
    Jun 2, 2022 at 20:19
  • $\begingroup$ @frakbak the obvious way would be by structuring the 0s and 1s in a way where there is room to fit that additional information. Perhaps by using every 2nd bit for data, and the bits in between for tracking state. $\endgroup$
    – user253751
    Jun 3, 2022 at 8:30
0
$\begingroup$

It can't overwrite the specification of $T_n$ itself

why wouldn't it? Part of that specification could include tape space for pseudo registers, instruction pointers or other scratch memory space that the turing machine needs to function.

But there is a simpler solution to writing to the left of $m$ (or right of $n$): copy the number over by one cell and then write into the newly created gap.

Improve this answer
$\endgroup$
1
  • $\begingroup$ There's no room in Penrose's Turing machine encoding for the things you suggest. The encoding just defines the states in a definite order, that's all. As for copying---I agree, but as I've asked in the question, how? How could the bookkeeping be done? $\endgroup$
    – frakbak
    May 31, 2022 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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