Editing Turing machine (section)

==Additional details required to visualise or implement Turing machines==
In the words of van Emde Boas (1990), p.&nbsp;6: "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 <math>\{L,R\}</math> to <math>\{L,R,N\}</math>, 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) in ''The Undecidable'', p.&nbsp;126–127 and Davis (2000) p.&nbsp;152):

: (definition 1): '''(q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>/E/N, L/R/N, q<sub>m</sub>)'''
:: '''(''' current state '''q<sub>i</sub>''' ''',''' symbol scanned '''S<sub>j</sub>''' ''',''' print symbol '''S<sub>k</sub>'''/erase '''E'''/none '''N''' ''',''' move_tape_one_square left '''L'''/right '''R'''/none '''N''' ''',''' new state '''q<sub>m</sub>''' ''')'''

Other authors (Minsky (1967) p.&nbsp;119, Hopcroft and Ullman (1979) p.&nbsp;158, Stone (1972) p.&nbsp;9) adopt a different convention, with new state '''q<sub>m</sub>''' listed immediately after the scanned symbol S<sub>j</sub>:
: (definition 2): '''(q<sub>i</sub>, S<sub>j</sub>, q<sub>m</sub>, S<sub>k</sub>/E/N, L/R/N)'''
:: '''(''' current state '''q<sub>i</sub>''' ''',''' symbol scanned '''S<sub>j</sub>''' ''',''' new state '''q<sub>m</sub>''' ''',''' print symbol '''S<sub>k</sub>'''/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.

{| class="wikitable" style="text-align: center"
|+ Example: state table for the 3-state 2-symbol busy beaver reduced to 5-tuples
! Current state
! Scanned symbol

! Print symbol
! Move tape
! Final (i.e. next) state
! 5-tuples
|-
| '''A'''
| 0

| 1
| R
| '''B'''
| ('''A''', 0, 1, R, '''B''')
|-
| '''A'''
| 1

| 1
| L
| '''C'''
| ('''A''', 1, 1, L, '''C''')
|-
| '''B'''
| 0

| 1
| L
| '''A'''
| ('''B''', 0, 1, L, '''A''')
|-
| '''B'''
| 1

| 1
| R
| '''B'''
| ('''B''', 1, 1, R, '''B''')
|-
| '''C'''
| 0

| 1
| L
| '''B'''
| ('''C''', 0, 1, L, '''B''')
|-
| '''C'''
| 1

| 1
| N
| '''H'''
| ('''C''', 1, 1, N, '''H''')
|}

In the following table, Turing's original model allowed only the first three lines that he called N1, N2, N3 (cf. Turing in ''The Undecidable'', p.&nbsp;126). He allowed for erasure of the "scanned square" by naming a 0th symbol S<sub>0</sub> = "erase" or "blank", etc. However, he did not allow for non-printing, so every instruction-line includes "print symbol S<sub>k</sub>" or "erase" (cf. footnote 12 in Post (1947), ''The Undecidable'', p.&nbsp;300). The abbreviations are Turing's (''The Undecidable'', p.&nbsp;119). Subsequent to Turing's original paper in 1936–1937, machine-models have allowed all nine possible types of five-tuples:

{| class="wikitable" style="text-align: center"
|-
!
! Current m-configuration<br />(Turing state)
! Tape symbol
! Print-operation
! Tape-motion
! Final m-configuration<br />(Turing state)
! 5-tuple
! 5-tuple comments
! 4-tuple
|-
| N1
| q<sub>i</sub>
| S<sub>j</sub>
| Print(S<sub>k</sub>)
| Left L
| q<sub>m</sub>
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, L, q<sub>m</sub>)
| {{CEmpty}} "blank" = S<sub>0</sub>, 1=S<sub>1</sub>, etc.
|
|-
| N2
| q<sub>i</sub>
| S<sub>j</sub>
| Print(S<sub>k</sub>)
| Right R
| q<sub>m</sub>
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, R, q<sub>m</sub>)
| {{CEmpty}} "blank" = S<sub>0</sub>, 1=S<sub>1</sub>, etc.
|
|-
| N3
| q<sub>i</sub>
| S<sub>j</sub>
| Print(S<sub>k</sub>)
| {{CNone|None N}}
| q<sub>m</sub>
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, N, q<sub>m</sub>)
| {{CEmpty}} "blank" = S<sub>0</sub>, 1=S<sub>1</sub>, etc.
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, q<sub>m</sub>)
|-
| 4
| q<sub>i</sub>
| S<sub>j</sub>
| {{CNone|None N}}
| Left L
| q<sub>m</sub>
| (q<sub>i</sub>, S<sub>j</sub>, N, L, q<sub>m</sub>)
|
| (q<sub>i</sub>, S<sub>j</sub>, L, q<sub>m</sub>)
|-
| 5
| q<sub>i</sub>
| S<sub>j</sub>
| {{CNone|None N}}
| Right R
| q<sub>m</sub>
| (q<sub>i</sub>, S<sub>j</sub>, N, R, q<sub>m</sub>)
|
| (q<sub>i</sub>, S<sub>j</sub>, R, q<sub>m</sub>)
|-
| 6
| q<sub>i</sub>
| S<sub>j</sub>
| {{CNone|None N}}
| {{CNone|None N}}
| q<sub>m</sub>
| (q<sub>i</sub>, S<sub>j</sub>, N, N, q<sub>m</sub>)
| Direct "jump"
| (q<sub>i</sub>, S<sub>j</sub>, N, q<sub>m</sub>)
|-
| 7
| q<sub>i</sub>
| S<sub>j</sub>
| Erase
| Left L
| q<sub>m</sub>
| (q<sub>i</sub>, S<sub>j</sub>, E, L, q<sub>m</sub>)
|
|
|-
| 8
| q<sub>i</sub>
| S<sub>j</sub>
| Erase
| Right R
| q<sub>m</sub>
| (q<sub>i</sub>, S<sub>j</sub>, E, R, q<sub>m</sub>)
|
|
|-
| 9
| q<sub>i</sub>
| S<sub>j</sub>
| Erase
| {{CNone|None N}}
| q<sub>m</sub>
| (q<sub>i</sub>, S<sub>j</sub>, E, N, q<sub>m</sub>)
|
| (q<sub>i</sub>, S<sub>j</sub>, E, q<sub>m</sub>)
|}

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 (cf. Post (1947), Boolos & Jeffrey (1974, 1999), Davis-Sigal-Weyuker (1994)); also see more at [[Post–Turing machine]].

===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:

{{blockquote|Thus the state of progress of the computation at any stage is completely determined by the note of instructions and the symbols on the tape. That is, the ''state of the system'' may be described by a single expression (sequence of symbols) consisting of the symbols on the tape followed by Δ (which is supposed to not to appear elsewhere) and then by the note of instructions. This expression is called the "state formula".|''The Undecidable'', pp. 139–140, emphasis added}}

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 (''The Undecidable'', p.&nbsp;121); this he calls "the ''complete configuration''" (''The Undecidable'', p.&nbsp;118). 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 [[Stephen Cole Kleene|Kleene]] shows how to write the [[Gödel number]] of a machine's "situation": he places the "m-configuration" symbol q<sub>4</sub> 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 "q<sub>4</sub>" itself as "the machine state" (Kleene, p.&nbsp;374–375). 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.&nbsp;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'''A'''1
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: ''B''01; 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.

Turing's biographer Andrew Hodges (1983: 107) has noted and discussed this confusion.

==="State" diagrams===

{|class="wikitable"
|+ The table for the 3-state busy beaver ("P" = print/write a "1")
|-
! Tape symbol
! colspan="3" | Current state A
! colspan="3" | Current state B
! colspan="3" | Current state C
|-
|
| Write symbol
| Move tape
| Next state
| Write symbol
| Move tape
| Next state
| Write symbol
| Move tape
| Next state
|-
| ''0''
| P
| R
| ''B''
| P
| L
| ''A''
| P
| L
| ''B''
|-
| ''1''
| P
| L
| ''C''
| P
| R
| ''B''
| P
| R
| ''HALT''
|}

[[File:State diagram 3 state busy beaver 2B.svg|thumb|500px|right|The "3-state busy beaver" Turing machine in a [[finite-state machine|finite-state representation]]. 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.&nbsp;74). They are more readily simulated by computer in tabular form (Booth, p.&nbsp;74). However, certain concepts—e.g. machines with "reset" states and machines with repeating patterns (cf. Hill and Peterson p.&nbsp;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.

[[File:Moves of a 3-state Busy Beaver.jpg|thumbnail|500px|right|The evolution of the busy beaver's computation starts at the top and proceeds to the bottom.]]

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"<!-- Stuation? Not Situation? Is that the right word? Yes, it is, cf. page 375 for example "The Godel number of the stiuation..." and then he shows a tape, etc. This usage runs throughout the chapter. wvbailey~~~~ --><!--So is it "stuation" or "stiuation"?-->, 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 (cf. Turing (1936) ''The Undecidable'', pp.&nbsp;139–140).