Turing machine
A Turing machine has two components:
- Central controller (where the states are)
- A unique accepting state
acc - A unique rejecting state
rej - All other states are non-terminal(!), meaning that the Turing machine will continue running until either in state
accorrej - Each transition between states is in the form of
, where is the direction, either R(right) or L(left). And are letters, is the current letter in the input line and is the letter to write into the input line.
- A unique accepting state
- Input line
- The input line can be navigated both forward and backward
- Input line spans infinitely both forward and backward, and all non-filled cells are considered to have a “space” character
- It is possible to write into the input line(!)