Turing’s Pristine Sequences

One source of von Neumann’s interest in the puzzles of complexity was the Turing Machine.'3 This breakthrough in the theory of computation was studied by many of the great mathematical minds of his generation.14 Von Neumann saw the Turing Machine as a useful model for explaining complexity, and a high-level understanding of the Turing Machine will set us up to join von Neumann as he probes the problem of self-reproduction.

Although it is called a machine, and although mathematicians often use mechanical diagrams as visual props to communicate the idea, the Turing Machine is not a machine at all. It is a formalized, self-referential system of sequences, and it has no necessary connection to the physical world of matter and energy. And, popular movies notwithstanding, the Turing Machine has nothing to do with the Enigma encryption device the Nazis used during World War II, which mathematician Alan Turing and his colleagues famously managed to decipher. A Turing Machine comprises three elements:

  • • A tape divided into cells into which one-dimensional sequences of symbols are written (typically, 0 and 1). The length of this tape is unlimited in both directions. (That the tape is infinite is our first clue that the Turing Machine is not a real device.)
  • • A read/write head to read the tape sequence one symbol at a time, either leaving the symbol unchanged or replacing it with its binary complement, and then moving the tape one cell to the left or to the right.
  • • A table of state transitions to define the specific calculation to be performed. The table determines the behavior of the Turing Machine at each step: read the symbol, change the symbol or leave it unchanged, move the tape left or right, and switch to some specific next state. There is also no upper limit on the size of the table of state transitions.

The Turing Machine is deterministic. The unique pairing of the symbol on the tape with the internal state specifies what happens next: whether the symbol is overwritten or left alone, whether the tape moves right or left, and the transition to a new state. To add two numbers, for example, they would be placed on the input tape and a table of state transitions would be defined for addition. The calculation would proceed and once completed the answer would appear on the tape. The procedure repeats until either it completes its calculation by reaching some final state (halting) or, for some computations like calculating the value of 77, it continues indefinitely.

As tedious and repetitive as it sounds, the power of the concept is its universality. With a suitably defined table of states, a Turing Machine can compute any mathematical function that can be computed, period. “Turing’s machines may be clumsy and slow,” writes computer scientist John Kemeny, “but they present the clearest picture of what a machine can do.”15 If you can express a problem in mathematical symbols, then a Turing Machine can be designed to compute it. This is called the Church-Turing Thesis; for computer scientists it is the definition of computability.16

As conceived earlier, Turing Machines do not scale well. Each kind of problem needs its own machine designed for that problem, just like the cell with its army of special-purpose enzymes. To solve all mathematical problems would demand an infinitely large fleet of Turing Machines. The cell partly solves this challenge with allosterism; enzymes can be configured to do more than one thing.17

Turing solves his scalability problem in much the same way, through what he calls the Universal Turing Machine (“UTM”). It eliminates the need for a fleet of unique machines; one machine can do it all. The UTM can be configured to behave like any special-purpose Turing Machine. Universality is possible because of a clever trick of sequential self-reference: the internal table of state transitions for a Turing Machine can be written in linear arrangements of the same zeros and ones used for its inputs and outputs. In other words, any Turing Machine can be completely described by a sequence on the tape of another Turing Machine, a UTM.18

Take a simple computation like addition on a desktop calculator. This calculation could be performed by a special-purpose Turing Machine, but it can also be performed by a UTM configured to behave like a desktop calculator. All that is needed is for the table of state transitions for the desktop calculator to be written as a sequence of zeros and ones on the input tape. This configures the UTM to behave as though it were a desktop calculator. It can then perform the desired computation, like addition or subtraction.

If this reminds you of the computers we encounter every day, it should. The UTM is the basis for every general-purpose stored-program digital computer in the world, from smartphones to servers in the cloud. The table of state transitions is what we call a program. Every time we open a program or fire up an app, we are configuring the universal general-purpose computer to behave as though it had been designed for some specific task. We even have little programs that cause our computers to behave like desktop calculators.

The Universal Turing Machine leads us back to von Neumann’s work on complexity. The UTM is an abstract, self-referential system of sequences.

Its inputs are one-dimensional patterns, its outputs are one-dimensional patterns, and it is itself written as a one-dimensional pattern. This means selfreproduction is not a conundrum for a UTM; all it needs to do is copy the zeros and ones of its own table of state transitions.

Von Neumann sees the Turing Machine as a good starting point. “For the question which concerns me here, that of‘self-reproduction’ of automata, Turing’s procedure is too narrow in one respect only,” he writes. “His automata are purely computing machines. Their output is a piece of tape with zeros and ones on it. What is needed for the construction to which I referred is an automaton whose output is other automata.”19

In other words, the computer, the physical UTM, is qualitatively different from the medium of its inputs and outputs. Reproducing the one-dimensional patterns of the software is not much of a challenge; the trick is reproducing the hardware. “I do not consider it essentially different whether the medium is a punched card, a magnetic wire, a magnetized metal tape with many channels on it, or a piece of film with points photographed on it,” von Neumann says. “In all these cases the medium which is fed to the automaton and which is produced by the automaton is completely different from the automaton.”20 Computers output patterns of zeros and ones; they do not output other computers.

However, when von Neumann looks at the biological world, he sees living things with the ability to produce outputs like themselves, to copy their hardware. “A complete discussion of automata,” he concludes, “can be obtained only by taking a broader view of these things and considering automata which can output something like themselves.”21