During a discussion with Boaz at work about Turing machines,1 I realised something new about them that I find rather fascinating. As a slogan: “The Read/Write Head Matters”; you don’t get Turing-equivalence just by adding unbounded memory to a state machine, you need just the right kind of addressing into that memory as well.2 If you grok this like I did, it’s almost obvious. Judging by Boaz’s reaction, if you don’t grok it like I did then it’s either wrong or uninteresting (or both). So here’s my attempt to enworden this little epiphany; hopefully someone else somewhere might get that sensation of little lights going on when they read it.

The naïve picture of a Turing machine, that I had until this discussion, is that it’s just a state machine with an unlimited memory store attached. Since we’re so familiar with random-access memory these days, it’s natural to picture this as a memory array, indexed by (say) integers. If you’ve simulated a Turing machine, that’s probably how you did it. (At least, it’s how I did it.) The “read/write head” is implemented as an index variable (giving the current position in the “tape” array), and “moving it” means incrementing or decrementing it.

Now of course if you intend this to completely represent a Turing machine, you run into unboundedness problems. Since a TM running a program can require unbounded tape space, there is some program out there that will require your TM to index into the array beyond the limit of the integer representation of whatever language you’re using for your simulation.3 “Of course,” you say at that point, “but it’s not a real Turing machine because our memory is limited.”

My epiphany is that this is not the same problem.

To get there, imagine that we decide to “improve” our TM simulation by allowing it random access to the memory. Instead of the operations shift left/right on the index register, we have simply goto (whichever value the index register currently holds). We should be able to access the same range of tape, without all that tiresome shuttling left and right! Once we work out how to put values into the index register.

Here’s where it falls apart. If those values come purely from the state machine component, then only boundedly many elements of the memory tape can be accessed: the memoryless state machine can only generate boundedly many distinct indices.4 This is still true even if you allow the state machine to use the current memory-cell value in generating its index, although that’s slightly trickier.5 What does work is to let the index calculation depend on the state machine plus the current index. (It’s easy to implement a shift-left/shift-right function, and then you’re back where you started from.) But that seems to be cheating: now you’ve got two unbounded memory stores, one for the tape and one for the index into the tape.6

Now here’s the interesting question: Where is this extra memory hiding in Turing’s formulation of the machine? And the answer: It’s in the position of the read/write head. That gives an arbitrary index into the unbounded memory. The crucial point is that this index is remembered (and can be operated on): it’s an extra kind of memory the machine has. And although the operations are bounded (left-shift/right-shift by only one cell), they are local to the current position (a relative addressing scheme) so given the persistence of the index they can accumulate unboundedly.

PS So how should you simulate your Turing machine to avoid this conceptual trap? Boaz suggested using a block of wood as the “pointer”, which works if you have a reliable supply of paper for the tape7 and don’t mind emigrating if the pointer crosses a national border at some point during your computation. If you prefer to stay digital, a two-stack machine does away with the implicit array-index in exactly the right way.

Notes:

  1. It started with news of a Turing machine implemented in Django’s templating language. Boaz was unimpressed: “Turing completeness isn’t that hard, Minesweeper is Turing-complete.” That can’t be right, I said, you mean Minesweeper is NP-complete. A game of Minesweeper is a problem to be solved, not a computational system. But I was wrong. [↪]
  2. Spoiler: what you need is a second unbounded memory for indexing, and bounded operations on that memory to manipulate it. Which is exactly what the read/write head gives you. Clever old Al’. [↪]
  3. Assuming you’re not using LISP or Python or whatever. Work with me here, I’m trying to make a rhetorical point, all right? [↪]
  4. Bounded by some calculation based on the number of states of the machine and the size of the alphabet. [↪]
  5. It seems as if there is potential for recursion: as you index more memory you can use it to store more state, thus allowing to index yet more memory. In fact, though, this isn’t the case. It’s easiest to see if you imagine a separate TM doing the address calculation. Its tape always starts blank: the only way it can vary its computation is based on which state the original machine is in, and what value the original machine is reading at that moment. But there are a fixed number of possibilities, based on the number of states the machine has and the size of the alphabet: that number is how many distinct computations the “address machine” can run on the empty tape, which is then the maximum number of distinct addresses it can generate. [↪]
  6. To formulate this precisely, imagine as in the previous note that we have an “address machine” that generates an address whenever the “main machine” requests one for a goto. If you spell out carefully how the two machines communicate, the argument of the previous note shows that the tape of the address machine must contain some kind of variable initial information when it is run. The previous address is just the most obvious candidate — you could also imagine the main machine “priming” the tape somehow —given a much more complicated control relationship between the two, since in this simple formulation the address machine runs a computation for every step the main machine takes— but this trivialises quickly into the main machine simply asking the address machine to perform the main machine’s own computation then reading off the result from the address it jumps to! [↪]
  7. You don’t have to start with an infinite tape, just arrange a contract with a paper factory guaranteeing to supply you with more whenever you need it. [↪]