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:
“Then the justice,
In fair round belly with good capon lined,
With eyes severe and beard of formal cut,
Full of wise saws and modern instances;
And so he plays his part.”
—William Shakespeare (1564–1616)
“Scientific method is the way to truth, but it affords, even in
principle, no unique definition of truth. Any so-called pragmatic
definition of truth is doomed to failure equally.”
—Willard Van Orman Quine (b. 1908)