In the words of van Emde Boas (1990): "The set-theoretical object [his formal seven-tuple description similar to the above] provides only partial information on how the machine will behave and what its computations will look like." For instance, • There will need to be many decisions on what the symbols actually look like, and a failproof way of reading and writing symbols indefinitely. • The shift left and shift right operations may shift the tape head across the tape, but when actually building a Turing machine it is more practical to make the tape slide back and forth under the head instead. • The tape can be finite, and automatically extended with blanks as needed (which is closest to the mathematical definition), but it is more common to think of it as stretching infinitely at one or both ends and being pre-filled with blanks except on the explicitly given finite fragment the tape head is on (this is, of course, not implementable in practice). The tape
cannot be fixed in length, since that would not correspond to the given definition and would seriously limit the range of computations the machine can perform to those of a
linear bounded automaton if the tape was proportional to the input size, or
finite-state machine if it was strictly fixed-length.
Alternative definitions Definitions in literature sometimes differ slightly, to make arguments or proofs easier or clearer, but this is always done in such a way that the resulting machine has the same computational power. For example, the set could be changed from \{L,R\} to \{L,R,N\}, where
N ("None" or "No-operation") would allow the machine to stay on the same tape cell instead of moving left or right. This would not increase the machine's computational power. The most common convention represents each "Turing instruction" in a "Turing table" by one of nine 5-tuples, per the convention of Turing/Davis (Turing (1936) and Davis (2000)): : (definition 1):
(qi, Sj, Sk/E/N, L/R/N, qm) ::
( current state
qi , symbol scanned
Sj , print symbol
Sk/erase
E/none
N , move_tape_one_square left
L/right
R/none
N , new state
qm ) Other authors (Minsky (1967), Hopcroft and Ullman (1979), Stone (1972), adopt a different convention, with new state
qm listed immediately after the scanned symbol Sj: : (definition 2):
(qi, Sj, qm, Sk/E/N, L/R/N) ::
( current state
qi , symbol scanned
Sj , new state
qm , print symbol
Sk/erase
E/none
N , move_tape_one_square left
L/right
R/none
N ) For the remainder of this article "definition 1" (the Turing/Davis convention) will be used. In the following table, Turing's original model allowed only the first three lines that he called N1, N2, N3. He allowed for erasure of the "scanned square" by naming a 0th symbol S0 = "erase" or "blank", etc. However, he did not allow for non-printing, so every instruction-line includes "print symbol Sk" or "erase". The abbreviations are Turing's. Subsequent to Turing's original paper in 1936–1937, machine-models have allowed all nine possible types of five-tuples: Any Turing table (list of instructions) can be constructed from the above nine 5-tuples. For technical reasons, the three non-printing or "N" instructions (4, 5, 6) can usually be dispensed with. For examples see
Turing machine examples. Less frequently the use of 4-tuples are encountered: these represent a further atomization of the Turing instructions.
The "state" The word "state" used in context of Turing machines can be a source of confusion, as it can mean two things. Most commentators after Turing have used "state" to mean the name/designator of the current instruction to be performed—i.e. the contents of the state register. But Turing (1936) made a strong distinction between a record of what he called the machine's "m-configuration", and the machine's (or person's) "state of progress" through the computation—the current state of the total system. What Turing called "the state formula" includes both the current instruction and
all the symbols on the tape: Earlier in his paper Turing carried this even further: he gives an example where he placed a symbol of the current "m-configuration" —the instruction's label— beneath the scanned square, together with all the symbols on the tape. He calls it "the
complete configuration". To print the "complete configuration" on one line, he places the state-label/m-configuration to the
left of the scanned symbol. A variant of this is seen in Kleene (1952) where
Kleene shows how to write the
Gödel number of a machine's "situation": he places the "m-configuration" symbol q4 over the scanned square in roughly the center of the 6 non-blank squares on the tape (see the Turing-tape figure in this article) and puts it to the
right of the scanned square. But Kleene refers to "q4" itself as "the machine state". Hopcroft and Ullman call this composite the "instantaneous description" and follow the Turing convention of putting the "current state" (instruction-label, m-configuration) to the
left of the scanned symbol (p. 149), that is, the instantaneous description is the composite of non-blank symbols to the left, state of the machine, the current symbol scanned by the head, and the non-blank symbols to the right.
Example: total state of 3-state 2-symbol busy beaver after 3 "moves" (taken from example "run" in the figure below): :: 1
A1 This means: after three moves the tape has ... 000110000 ... on it, the head is scanning the right-most 1, and the state is
A. Blanks (in this case represented by "0"s) can be part of the total state as shown here:
B01; the tape has a single 1 on it, but the head is scanning the 0 ("blank") to its left and the state is
B. "State" in the context of Turing machines should be clarified as to which is being described: the current instruction, or the list of symbols on the tape together with the current instruction, or the list of symbols on the tape together with the current instruction placed to the left of the scanned symbol or to the right of the scanned symbol.
"State" diagrams . Each circle represents a "state" of the table—an "m-configuration" or "instruction". "Direction" of a state
transition is shown by an arrow. The label (e.g.
0/P,R) near the outgoing state (at the "tail" of the arrow) specifies the scanned symbol that causes a particular transition (e.g.
0) followed by a slash
/, followed by the subsequent "behaviors" of the machine, e.g. "
P print" then move tape "
R right". No general accepted format exists. The convention shown is after McClusky (1965), Booth (1967), Hill, and Peterson (1974). To the right: the above table as expressed as a "state transition" diagram. Usually large tables are better left as tables (Booth, p. 74). They are more readily simulated by computer in tabular form (Booth, p. 74). However, certain concepts—e.g. machines with "reset" states and machines with repeating patterns (cf. Hill and Peterson p. 244ff)—can be more readily seen when viewed as a drawing. Whether a drawing represents an improvement on its table must be decided by the reader for the particular context. The reader should again be cautioned that such diagrams represent a snapshot of their table frozen in time,
not the course ("trajectory") of a computation
through time and space. While every time the busy beaver machine "runs" it will always follow the same state-trajectory, this is not true for the "copy" machine that can be provided with variable input "parameters". The diagram "progress of the computation" shows the three-state busy beaver's "state" (instruction) progress through its computation from start to finish. On the far right is the Turing "complete configuration" (Kleene "situation", Hopcroft–Ullman "instantaneous description") at each step. If the machine were to be stopped and cleared to blank both the "state register" and entire tape, these "configurations" could be used to rekindle a computation anywhere in its progress. ==Equivalent models==