Show that, for any Turing-recognizable L, there is an unrestricted grammar that generates L. (Hint: We showed in class how to represent the configuration of a Turing machine as a string. At each step, the configuration of the machine changes. Think about how the string representing the configuration changes correspondingly, and represent this using grammar

Sol35:

Let M be a Turing machine that recognizes language L. We can construct an unrestricted grammar G that generates L as follows:

1. Let Q be the set of states of M, and let S be the tape alphabet of M (including the blank symbol). We will use the symbols {q0, q1, ..., qk} to represent the states of M, and the symbols {a1, a2, ..., an} to represent the tape alphabet.
2. We can represent the configuration of M at any given time as a string of the form "qiajv", where qi is the current state of M, aj is the symbol on the tape under the tape head, and v is the portion of the tape to the right of the tape head.
3. We can then represent the computation of M on any given input w as a sequence of configurations, C1, C2, ..., Cn, where C1 is the initial configuration of M on input w, and each Ci is obtained from Ci-1 by applying the transition function of M.
4. We can now construct a set of production rules for G that generate all strings of the form "qiajv" that represent valid configurations of M. Specifically, for each transition function d(qi, aj) = (qj, ak, L/R), we add the following production rule to G:

qi a j v ? a k q j v if L v a j q i ? v q j a k if R

These rules essentially represent the movement of the tape head to the left or right, along with the change in state and symbol on the tape.

1. Finally, we add two additional production rules to G: one that generates the initial configuration of M on input w, and one that generates the accept configuration of M (i.e., the configuration in which M enters an accept state). These production rules can be constructed using the symbols and rules from steps 1-4.

With these production rules, G can generate all strings of the form "qiajv" that represent valid configurations of M on input w, and therefore, can generate all strings in L. Thus, G is an unrestricted grammar that generates L.