next up previous contents index
Next: The universal Turing machine: Up: Turing machines Previous: Turing machines as language   Contents   Index


Turing machines as function computers:

TM may compute partial functions mapping natural numbers into natural numbers (Hopcroft and Ullman, 1979, 151). A possible construction uses $\Sigma=\{1\}$ and zero (0) as the blank $B$. If the function computed by the TM is $f$, and the initial tape is $11\ldots 10000\ldots$ with $n$ ones, the result is $0000\ldots011\ldots10000\ldots$ with $f(n)+1$ ones if $f$ is defined for $n$ and with zero ones if undefined. Any recursively computable function mapping naturals into naturals may be simulated by a Turing machine.



Debian User 2002-01-21