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:
“On every formal visit a child ought to be of the party, by way of provision for discourse.”
—Jane Austen (1775–1817)
“The physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.”
—Ralph Waldo Emerson (1803–1882)