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 spiritual kinship between Lincoln and Whitman was founded upon their Americanism, their essential Westernism. Whitman had grown up without much formal education; Lincoln had scarcely any education. One had become the notable poet of the day; one the orator of the Gettsyburg Address. It was inevitable that Whitman as a poet should turn with a feeling of kinship to Lincoln, and even without any association or contact feel that Lincoln was his.”
—Edgar Lee Masters (1869–1950)
“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)