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 and zero (0) as the blank
. If the function computed
by the TM is , and the initial
tape is
with ones, the result is
with ones if is defined
for 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