next up previous contents index
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 $w\in\Sigma^*$ at the beginning of the tape and blanks $B$ after it. A TM accepts a string $w$ when it enters a final state in $F$; 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