[Overview] [Previous] [Next]
We have shown that a Turing machine can do anything that an unrestricted grammar can do. Now we have to show that an unrestricted grammar can do anything a Turing machine can do. This can be done by using an unrestricted grammar to emulate a Turing machine. We will give only the barest outline of the proof.
Recall that a configuration of a Turing machine can be written as a string
where the x's are the symbols on the tape, qm is the current state, and the tape head is on the square containing xk (the symbol immediately following qm). It makes sense that a grammar, which is a system for rewriting strings, can be used to manipulate configurations, which can easily be written as strings.
A Turing machine accepts a string w if
for some strings x and y and some final state qf, whereas a grammar produces a string if
Because the Turing machine starts with w while the grammatical derivation ends with w, the grammar we build will run "in reverse" as compared to the Turing machine.
Copyright © 1996 by David Matuszek
Last modified Apr 8, 1996