Editing Turing machine (section)

==Formal definition==
Following {{harvtxt|Hopcroft|Ullman|1979|p=148}}, a (one-tape) Turing machine can be formally defined as a 7-[[tuple]] <math>M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math> where
* <math>\Gamma</math> is a finite, non-empty set of ''tape alphabet symbols'';
* <math>b \in \Gamma</math> is the ''blank symbol'' (the only symbol allowed to occur on the tape infinitely often at any step during the computation);
* <math>\Sigma\subseteq\Gamma\setminus\{b\}</math> is the set of ''input symbols'', that is, the set of symbols allowed to appear in the initial tape contents;
* <math>Q</math> is a finite, non-empty set of ''states'';
* <math>q_0 \in Q</math> is the ''initial state'';
* <math>F \subseteq Q</math> is the set of ''final states'' or ''accepting states''. The initial tape contents is said to be ''accepted'' by <math>M</math> if it eventually halts in a state from <math>F</math>.
* <math>\delta: (Q \setminus F) \times \Gamma \rightharpoonup Q \times \Gamma \times \{L,R\}</math> is a [[partial function]] called the ''transition function'', where L is left shift, R is right shift. If <math>\delta</math> is not defined on the current state and the current tape symbol, then the machine halts;<ref>p.149; in particular, Hopcroft and Ullman assume that <math>\delta</math> is undefined on all states from <math>F</math></ref> intuitively, the transition function specifies the next state transited from the current state, which symbol to overwrite the current symbol pointed by the head, and the next head movement.

[[File:Busy Beaver 3 State.png|thumb|3-state Busy Beaver. Black icons represent location and state of head; square colors represent 1s (orange) and 0s (white); time progresses vertically from the top until the '''HALT''' state at the bottom.]]

A variant allows "no shift", say N, as a third element of the set of directions <math>\{L,R\}</math>.

The 7-tuple for the 3-state [[busy beaver]] looks like this (see more about this busy beaver at [[Turing machine examples]]):
* <math>Q = \{ \mbox{A}, \mbox{B}, \mbox{C}, \mbox{HALT} \}</math> (states);
* <math>\Gamma = \{ 0, 1 \}</math> (tape alphabet symbols);
* <math>b = 0</math> (blank symbol);
* <math>\Sigma = \{ 1 \}</math> (input symbols);
* <math>q_0 = \mbox{A}</math> (initial state);
* <math>F = \{ \mbox{HALT} \}</math> (final states);
* <math>\delta =</math> see state-table below (transition function).

Initially all tape cells are marked with <math>0</math>.

{| class="wikitable" style="text-align:center"
|+ State table for 3-state, 2-symbol busy beaver
! rowspan="2" | Tape symbol
! colspan="3" | Current state A
! colspan="3" | Current state B
! colspan="3" | Current state C
|- style="font-size:9pt"
| Write symbol
| Move tape
| Next state
| Write symbol
| Move tape
| Next state
| Write symbol
| Move tape
| Next state
|-
| 0
| 1
| R
| '''B'''
| 1
| L
| '''A'''
| 1
| L
| '''B'''
|-
| 1
| 1
| L
| '''C'''
| 1
| R
| '''B'''
| 1
| R
| '''HALT'''
|}