Next: Procedures and Functions
Up: Background for Decidability
Previous: Background for Decidability
A Turing machine is composed of an infinite tape bounded on the left,
a read-write tape head, and a finite control.
A Turing Machine (TM) is described by the tuple
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.