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: