Next: instantaneous description of Turing
Up: Ben's presentation
Previous: Black Box digression
A Turing Machine (TM) is described by
|  |
(5) |
where
- Q
- is the finite set of states,
- is the the finite set of allowable tape symbols,
- B
- is the blank symbol (
).
- is the set of input symbols,
.
- is the next move function,
. - q0
- is the start state (
).
- F
- is the set of final states,
.
For each symbol scanned, a TM:
- 1.
- changes state,
- 2.
- prints a symbol on tape cell, replacing what was written there
before, and
- 3.
- moves the tape head left or right one cell.
root
6/8/1998