I. Definitions

1. Turing Machine Theory

• The purpose of the theory of Turing machines is to prove that certain specific languages have no algorithm.

• Start with a language about Turing machines themselves.

• Reductions are used to prove more common questions undecidable.

  Only decidable algorithm can have complexibility

2. Features

1. R / W head, which make it possible to either read or modify input string
2. Bidirection infinite tape

3. Formalism

$$ M=(Q, \Sigma, \Gamma, \delta, q_0, B, F) $$

where:

• $Q$: The finite set of states

• $\Sigma$: An input alphabet

• $\Gamma$: A tape alphabet (contains $\Sigma$)

• $\delta$: A transition function.

  The arguments of $\delta(q,X)$ are a state $q$ and a tape symbol $X$.

  The value of $\delta(q,X)$ is either undefined or a triple $(p,Y,D)$, where:

  • $p$: the next state, in $Q$
  • $Y$: the symbol in $\Gamma$, written in the cell being scanned (replace any existed)
  • $D$: direction in which the head moves, either L or R. (may add $H / \lambda$ for hold)

• $q_0$: A start symbol (in $Q$)

• $B$: A blank symbols (in $\Gamma - \Sigma$)

  • All tape except for the input is blank initially.

• $F$: A set of final states (in $Q$)