Turing Machines

A Very Simple Machine

Imagine a linear tape that stretches off indefinitely in either direction in some otherwise featureless landscape. Regular lines are drawn across the width of the tape. Call the spaces between the lines 'cells'. Each cell is either blank or has an 'X' marked on it, and trundling along the tape is a contraption resembling a small boxcar. The boxcar moves in fits: it starts on a cell, moves to an adjacent cell, and stops. Indeed, there are only four things the boxcar can do. It can move one cell to the left or one cell to the right, it can erase an 'X' if there is one on the cell beneath it, and it can write an 'X' if the cell is blank.

The boxcar itself need not be closed to inspection. Opening the top might reveal a system of gears and levers which looks for all the world like the guts of a player-piano. Running through the gears would be an instruction tape of some finite length. The instruction tape would have cutouts to determine the next step, where 'the next step' includes the next position of the internal gearing and whether the boxcar writes an 'X', erases an 'X', or moves to an adjacent cell, depending on both the position of the gears and whether or not the current cell had an 'X'. We can therefore describe each step by a simple quadruple. Let each of q₁, q₂,..., q_n be a unique position or 'state' of the gears. Suppose 'X' denotes the operation of writing an X, 'B' (for 'blank') denotes the operation of erasing an X, 'L' denotes moving to the left one cell, and 'R' denotes moving to the right one cell. Then the set of quadruples,

q₁BXq₁, q₁XRq₂, q₂XBq₂, q₂BRq₃, q₃BXq₃, q₃XRq₄, q₄XBq₄, q₄BRq₅,

describe a situation in which the boxcar, in state q₅, will be sitting directly to the right of four squares which alternate X, blank, X, blank. A graphical description such as the one in figure 1 is equally complete and simpler to follow.

Turing Machines

The instruction tape, the boxcar, and the linear tape upon which it operates together make up a simple variant of the Turing Machine. To be sure, there is nothing special about blanks and X's. In some incarnations, Turing Machines read and write 1's and 0's. Any string of characters - or any sequence of strings of characters separated by blanks - are fodder for a properly configured Turing Machine. A few conventions prove useful if we are to get a handle on the gamut of Turing Machines. First, a Turing Machine is in an initial configuration when, and only when, it is reading the left-most character of the left-most string in a sequence of strings, and 'q₀' denotes the state of the Turing Machine in initial configuration. And second, a Turing Machine is in a final configuration when, and only when, it halts on the right-most character of the right-most string of a sequence of strings. We shall say that a Turing Machine which has achieved a final configuration has computed its input, where its input is understood to be the sequence of strings from its initial configuration and its output is understood to be the sequence of strings upon entering its final configuration. The idea behind these conventions is simply that a Turing Machine should 'read' from left to write.

There are two ways in which a Turing Machine can fail to compute its input. A Turing Machine can either halt in something other than final configuration or not halt at all. A Turing Machine which fails to halt has one of two problems: either it is reading off in one or another direction indefinitely, or it is in some endless, usually complicated, loop across a sequence of strings. Let us say that a Turing Machine which halts in something other than final configuration has rejected its input. To illustrate failure to compute, suppose that we want a Turing Machine that computes the difference between two numbers. So as to favor a numerical frame of mind, replaces X's with 1's. The input to the machine will be two strings of 1's separated by a single blank. Its output should be a single string of 1's whose length is the difference of the first input string's length by the second input string's length.

To compute 5 - 3, for example, we want a Turing Machine which takes as input

11111_111

and outputs

11

One way to do this is to read right until the Turing Machine crosses the blank and gets to the first character of the second string, erase, move back to the last character of the first string, erase, and repeat. In effect, the Turing Machine nibbles each string equally from the inside out. The problem is that once it has nibbled the third character of the first string, it will then read back to the right to find that there is no next character in the second string (the second string having been nibbled entirely away). Whereupon the Turing Machine will fail to compute because it will unendingly read to the right.

A far better approach would be to have the Turing Machine read across the second string to the last character, erase it, then back up to the first character of the first string, erase it, and repeat. The Turing Machine thus nibbles from the outside in until it halts, in state q₃, in final configuration - whereupon it will have computed its input, as in Figure 2. But there is a problem with this Turing Machine. Suppose that the first string in the input is shorter than the second string. The Turing Machine will nibble away until the first string is entirely gone and halt in state q₈ on the second blank to the left of the remainder of the second string. Since the Turing Machine fails to halt in final configuration, it rejects its input. The Turing Machine computes subtraction on the Natural Numbers only. The Integers, which include negative numbers, are beyond its purview. A more complicated Turing Machine could, however, be constructed to handle subtraction on the Integers.

In summary, a Turing Machine fails compute when it loops endlessly (or wanders off aimlessly) or when it fails to halt in standard configuration. Let us say that a function is Turing Machine-computable just in case there is a Turing Machine that computes it.

A Brief Taxonomy of Turing Machines

As the previous examples demonstrate, Turing Machines can vary according to the characters they can read. Such a difference between Turing Machines is not of any particular theoretical importance, since a Turing Machine which reads 1's and blanks is essentially the same from a design standpoint as a Turing Machine which reads the entire alphabet. The design is called an 'infinite single-tape deterministic Turing Machine'. The Turing Machines are infinite single-tape for the obvious reason that they accept input and provide output on a single linear tape of indefinite length. The Turing Machines are also deterministic because their flow-charts exactly predict what they will do in a given state while reading a given character. Equivalently, the Turing Machines are deterministic because they behave in some way with probability 1 in any given configuration.

Because the length of tape in an infinite Turing Machine is indefinite - i.e., for any input, it is as long in either direction as need be for the Turing Machine to compute the input, or fail to compute the input, as the case may be - such Turing Machines effectively have an infinite memory capacity. Turing Machines of this type are in principle an idealized model of computation; their finite variations become important when we consider real-world limitations on memory.

A multi-tape Turing Machine operates with more than one linear tape, and the variations within this group are extensive. For instance, one type of multi-tape Turing Machine can read from one tape and write to a second tape. Another type reads and writes to each of two tapes, while still another has a third 'memory' tape upon which the Turing Machine makes reminder marks. In each case there is but one boxcar shuttling across the parallel tapes. The boxcar can be made as wide as necessary to accommodate as many tapes as needed.

It is possible, however, for a Turing Machine to include more than one boxcar. Consider that all of the Turing Machines we've discussed so far have been constrained in a fairly obvious way: in any state, there is at most one action specified for each character read (including blanks). When the Turing Machine in Figure 3 is in state q₁ reading a 1, for instance, the boxcar moves right a cell. But suppose we had a second choice: reading a 1 in state q₁, move left a cell and enter state q₅ (Figure 4 shows the relevant bit.)

The Turing Machine reading 1 in q₁ has to choose between moving left to enter q₅ and moving right to enter q₄. The obvious solution would be stochastic; flip a coin - heads go left, tails go right. Notice that employing this solution amounts to rejecting determinism altogether; we now have indeterministic Turing Machines (sometimes called 'probabilistic' Turing Machines.) An indeterministic Turing Machine no longer simply computes or rejects if it halts. Rather, it computes with some probability such that, for indeterministic Turing Machine m which halts on input w,

Pr[m rejects w] = 1 - Pr[m computes w].

Handling the puzzle in Figure 4 with an indeterministic Turing Machine is, as I say, an obvious solution. A non-obvious solution is to go ahead and choose both ways at once in a mechanistic analogue of having your cake and eating it too. The idea is that upon entering q₁ and reading 1, the Turing Machine splits or spawns itself into two identical configurations. The Turing Machine is now composed of two identical linear tapes, two identical instruction tapes, and two identical boxcars in the same state. One might think of these as 'child' Turing Machines which belong to, or are a part of, the original 'parent' Turing Machine. One child goes left, the other right. Other choices might occur later for one or both of the children, so in theory the parent Turing Machine must be able to spawn as many child Turing Machines as necessary to exhaust all the choices. The parent-child metaphor is useful, but it should be emphasized that we don't in fact have separate Turing Machines. Rather, we have a single Turing Machine which has been cleverly designed to employ multiple tapes, boxcars, and instruction tapes as needed. Such Turing Machines are nondeterministic, following Sipser (1997, pp. 138-140). A nondeterministic (parent) Turing Machine which halts on an input if all of its children halt, computes its input if any of its children do, and rejects its input if it halts but no child computes.