next up previous contents index
Next: Turing machines as language Up: Turing computability with DTRNN Previous: Turing computability with DTRNN   Contents   Index


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



Subsections
next up previous contents index
Next: Turing machines as language Up: Turing computability with DTRNN Previous: Turing computability with DTRNN   Contents   Index
Debian User 2002-01-21