Formal Definition
Hopcroft and Ullman (1979, p. 148) formally define a (one-tape) Turing machine as a 7-tuple where
- is a finite, non-empty set of states
- is a finite, non-empty set of the tape alphabet/symbols
- is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
- is the set of input symbols
- is the initial state
- is the set of final or accepting states.
- is a partial function called the transition function, where L is left shift, R is right shift. (A relatively uncommon variant allows "no shift", say N, as a third element of the latter set.)
Anything that operates according to these specifications is a Turing machine.
The 7-tuple for the 3-state busy beaver looks like this (see more about this busy beaver at Turing machine examples):
- ("blank")
- (the initial state)
- see state-table below
Initially all tape cells are marked with 0.
| Tape symbol | Current state A | Current state B | Current state C | ||||||
|---|---|---|---|---|---|---|---|---|---|
| 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 |
Read more about this topic: Turing Machine
Famous quotes containing the words formal and/or definition:
“The bed is now as public as the dinner table and governed by the same rules of formal confrontation.”
—Angela Carter (1940–1992)
“The man who knows governments most completely is he who troubles himself least about a definition which shall give their essence. Enjoying an intimate acquaintance with all their particularities in turn, he would naturally regard an abstract conception in which these were unified as a thing more misleading than enlightening.”
—William James (1842–1910)