## Turing Machines

A Turing machine is a model of what a computer can solve, and what it cannot solve.

The machine contains a tape, which is infinite in both directions.

• Each cell of the tape holds one symbol.
• The tape alphabet is the finite set of symbols for the tape.
• The tape holds both input and output.
• The machine has a finite number of internal states, $1$ to $k$.

Visualization of a Turing Machine tape.

• The machine examines the current tape symbol and current state
• It then writes the new tape symbol, changes the state and moves left or right one cell.
• The instructions are stored as a tuple.

$$\text{([if state] [if value] [set value] [set state] [move direction])}$$

• It usually starts in state $1$.
• It always starts reading from the leftmost non-blank symbol in the input unless specified otherwise.
• If no rule applies, the machine halts.

There are two main reasons why an instruction is invalid.

• There should be no two rules with the same $\text{if state}$ and $\text{if value}$.
• The state cannot be set to blank.