Equivalence of Unrestricted Grammars and Turing Machines

Learn why unrestricted grammars and Turing machines are equivalent.

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 TM\text{TM} that recognizes (but not necessarily decides) its language or performs its function. To create a TM\text{TM} for an unrestricted grammar, we can use a nondeterministic TM\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:

Get hands-on with 1200+ tech skills courses.