[Overview] [Previous] [Next]

From Turing Machines To Grammars I

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

q0w move zero or more times to xqfy

for some strings x and y and some final state qf, whereas a grammar produces a string if

S derives 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