next up previous contents index
Next: Linearly-bounded automata Up: Turing machines Previous: Turing machines as function   Contents   Index


The universal Turing machine:

All TMs of the form

\begin{displaymath}M=(Q,\{0,1\},\{0,1,B\},\delta,q_1,B,\{q_2\})\end{displaymath}

may be encoded as strings over $\{0,1\}$ and written, followed by the string $w$ to be processed, into a tape. There exists a special Turing machine called the universal Turing machine (UTM, Hopcroft and Ullman (1979, 181), Salomaa (1973, 117)) which will read this tape and simulate $M$ on $w$.



Debian User 2002-01-21