How can I convert the Turing machine the recognizes language $L$ into an unrestricted grammar?

According to this Wikipedia article, unrestricted grammars are equivalent to Turing machines. The article notes that I can convert any Turing machine into an unrestricted grammar, but it only shows how to convert a grammar to a Turing machine.

How do I indeed do that and convert the Turing machine the recognizes language $L$ into an unrestricted grammar? I have tried replacing transition rules with grammar rules, but a Turing machine can have many different configurations of states as well...

We encode the Turing machine's tape content in sentential forms; a special set of non-terminals encodes the current state. There can only be one of them in the sentential form at any point in time, placed to the right of the symbol the TM is currently pointing at.

The second crucial idea is that we have to reverse the process: TMs take the word as input and convert it to $1$ or $0$, or they don't terminate. The grammar, however, has to generate the word. Luckily, grammars are inherently non-deterministic, so we can just let it "guess" where the accepting $1$ came from; all words that cause the TM to accept can be generated then.

Let $\cal{Q} = \{Q_0,\dots,Q_k\}$ the set of state-nonterminals; w.l.o.g. let $Q_0$ be the starting-state-nonterminal and $\cal{Q}_F \subseteq \cal{Q}$ the set of accepting-states-nonterminals. First, we need starting rules that generate all possible accepting configurations:

$\qquad \displaystyle S \to \#1Q_f\# \qquad$ for all $Q_f \in \cal{Q}_F$.

Similarly, we terminate when we "reach" the starting state in the correct position, namely on the first symbol:

$\qquad \#aQ_0 \to \#a \qquad$ for all $a \in \Sigma$.

Translating the actual state transitions is straight-forward:

\qquad \begin{align} aQ &\to cQ' \qquad\ \,\text{ for } a,c \in \Sigma \land (a,Q,N) \in \delta(c,Q') \\ aQb &\to acQ' \qquad \text{ for } a,b,c \in \Sigma \land (b,Q,L) \in \delta(c,Q') \\ abQ &\to cQ'b \qquad\, \text{ for } a,b,c \in \Sigma \land (a,Q,R) \in \delta(c,Q') \end{align}

There are some technical kinks to iron out; for instance, you have to get rid of the boundary markers $\#$ at the end. That can be done by spawning two special nonterminals instead of terminating, swapping those to the ends and then removing the $\#$ along with them. Furthermore, more $\#$ have to be created on demand; that requires some hacking of the rules with $d=\#$.

Also, the construction becomes a bit more complicated if the TM uses non-input symbols. In that case, the termination rules may be wrong: if there are non-input symbols somewhere on the tape, we have not generated a proper word. This can be fixed similarly to removing $\#$: spawn a special non-terminal from $Q_0$ that is swapped to the right and only removed if all symbols are from $\Sigma$.

• how does the produced string increase in length though? From what you've shown the most it can really be is just 1 non-terminal long at the end
– M Z
Commented Oct 26, 2020 at 23:05
• @MZ Huh. Good question. :facepalm: Adding $Q \to aQ$ for all $a \in \Sigma, Q \in \mathcal{Q}$ does it, right? Commented Oct 28, 2020 at 9:59
• Or rather, $\#a \to \#ba$ and $a\# \to ab\#$? Commented Oct 28, 2020 at 11:19
• FWIW 1: It seems I left out the detail of creating new symbols explicitly (see second-to-last paragraph;). I think the trade-off is okay; I don't give a full construction (let alone proof) but the basic idea. The text could have been clearer, granted. Commented Oct 28, 2020 at 11:26
• FWIW 2: Not sure why rule schemas 2 and 3 are not symmetrical. :thinking-face: Commented Oct 28, 2020 at 11:26

Here's another way to do it without going in reverse.

Assume WLOG that the Turing Machine clears the tape before accepting and has special markers $$\triangleright, \triangleleft$$ denoting the start and end of the tape that is in use. Furthermore, assume that there is a single accept state, so that the unique accepting configuration is $$\triangleright q_{accept} \triangleleft$$. The strategy will then be to start with $$\triangleright q_{start} w \triangleleft w$$, simulate the TM with the rules of the grammar (within $$\triangleright, \triangleleft$$) and then send $$\triangleright q_{accept} \triangleleft \to \epsilon$$.

The start variable of the grammar has the following rule $$S \to \triangleright q_{start} B.$$

Where $$B$$ is the start symbol for a grammar generating $$\{w \triangleleft w: w \in \Sigma^*\}$$ (Check here for a reference on how to do this.)

For each transition of the form $$\delta(q, a) = (q', a', R)$$ have the rule

$$qa \to a'q'$$

For each transition of the form $$\delta(q, a) = (q', a', L)$$ have the rule

$$bqa \to q'ba'$$

Following the convention that going left past the end of left end of the tape makes you stay in place you also need rule $$\triangleright q a \to \triangleright q' a'$$.

Also, allow the tape to extend to the right if needed using the rule $$\triangleleft \to \sqcup \triangleleft$$, and allow the tape to shorten with $$\sqcup \triangleleft \to \triangleleft$$. You can show by induction that the configuration at of the Turing machine is exactly the intermediate string generated by the grammar after any number of steps.

$$\triangleright q_{accept} \triangleleft \to \epsilon.$$
So that for any $$w \in L(M)$$,
$$S \to ... \to \triangleright q_{start} w \triangleleft w \to ... \to \triangleright q_{accept} \triangleleft w \to w.$$
If $$w \notin L(M)$$, we never reach $$\triangleright q_{accept} \triangleleft$$, and the grammar never terminates.