Next: instantaneous description of Turing
Up: Ben's presentation
Previous: Black Box digression
A Turing Machine (TM) is described by
For each symbol scanned, a TM:
- is the finite set of states,
- is the the finite set of allowable tape symbols,
- is the blank symbol ().
- is the set of input symbols, .
- is the next move function, .
- is the start state ().
- is the set of final states, .
- changes state,
- prints a symbol on tape cell, replacing what was written there
- moves the tape head left or right one cell.