Editing Turing machine (section)

===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]].