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:
“Good gentlemen, look fresh and merrily.
Let not our looks put on our purposes,
But bear it as our Roman actors do,
With untired spirits and formal constancy.”
—William Shakespeare (1564–1616)
“The definition of good prose is proper words in their proper places; of good verse, the most proper words in their proper places. The propriety is in either case relative. The words in prose ought to express the intended meaning, and no more; if they attract attention to themselves, it is, in general, a fault.”
—Samuel Taylor Coleridge (1772–1834)