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

x_{i}...x_{j}q_{m}x_{k}...x_{l}

where the x's are the symbols on the tape, q_{m} is the current state, and the
tape head is on the square containing x_{k} (the symbol immediately following q_{m}).
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

q_{0}w
xq_{f}y

for some strings x and y and some final state q_{f}, whereas a grammar produces
a string if

S w.

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