Next: Turing machines as function
Up: Turing machines
Previous: Turing machines
  Contents
  Index
Turing machines as language acceptors:
The TM is started on a tape containing a string at
the beginning of the tape and blanks after it. A TM accepts a string when it enters a final
state in ; if the string is not accepted, the
TM may or may not stop. It may be shown
(Hopcroft and Ullman (1979, 221); Salomaa (1973, 37)) that the
class of languages accepted by TM is the same as
the class of languages generated by unrestricted
grammars (defined in
section 4.1.2).
Debian User
2002-01-21