Turing machines

A Turing machine ((Turing, 1936); Hopcroft and Ullman (1979, 147); Salomaa (1973, 36)) is an automaton that uses an endless tape as memory. Any finite procedure, algorithm, or computable function may always be reduced to a Turing machine (TM).

In each move, the machine reads a symbol from the tape. Depending on the symbol and the current state, the TM changes state, writes a new symbol, and moves right or left.

A TM may be defined as $M=(Q,\Sigma,\Lambda,\delta,q_I,B,F)$ where

• $Q$ is a finite set of states;
• $\Sigma$ is the input alphabet;
• $\Lambda$ is the tape alphabet;
• $\delta:Q\times\Lambda\rightarrow Q\times\Lambda\times\{L,R\}$ is the next move function ($R$ is ``right'', $L$ is ``left''; the function may not be defined for some arguments; there, the TM stops);
• $q_I\in Q$ is the initial state;
• $B\in \Lambda$ ( $B\not\in\Sigma$) is a special blank symbol;
• $F\subset Q$ is the set of final states (the machine stops when entering any $q\in F$).