Equivalence of Unrestricted Grammars and Turing Machines

Constructing a Turing machine for an unrestricted grammar

As we know, the behavior of unrestricted grammars is procedural, and any procedure can be simulated by a Turing machine. Therefore, for every unrestricted grammar there is a $\text{TM}$ that recognizes (but not necessarily decides) its language or performs its function. To create a $\text{TM}$ for an unrestricted grammar, we can use a nondeterministic $\text{TM}$ with four tapes/memory areas that contain the following:

• Tape 1 holds the string to accept or reject.
• Tape 2 contains the ongoing, working derivation.
• Tape 3 holds all the left-hand sides of the grammar rules.
• Tape 4 holds all the right-hand sides of the grammar rules, in the same order that the left-hand sides appear on Tape 3.

To begin a derivation, we place the start variable, or starting configuration if we are simulating a function, on Tape 2, and execute the following logic:

If we place an invalid string on Tape 1, the procedure does not halt, but it halts on every valid input. This shows that the language of an unrestricted grammar is recursively enumerable. Likewise, any computational grammar can be simulated by a $\text{TM}$ by placing the input on Tape 1 before running the machine.

Remember: For every unrestricted grammar, there is a Turing machine that recognizes the same language or performs the same function.

Converting a TM to an unrestricted grammar

Going the other direction, it is straightforward to construct a computational grammar for a $\text{TM}$ by rewriting the $\text{TM}$'s transitions in grammatical form, using the states as variables. Let’s look at a few examples to understand the construction of unrestricted grammar for a $\text{TM}$.

Example 1

Consider the following $\text{TM}$ for adding two unary numbers.

Let’s convert this $\text{TM}$ to computational grammar. We repeat the transitions below in functional form. Note that the ...