(Notes from Chapter 7, Sections 1 - 2)
Given a pair of words \(g, \overline{g}\) on some alphabet, the expression \[ g \rightarrow \overline{g}\] is called a semi-Thue production. The term rewrite rule is also used.
If \(P\) is the semi-Thue production \(g \rightarrow \overline{g}\), then \[u \mathop{\Rightarrow}_P v\] means that there are (possibly null) words \(r,s\) such that \[u = rgs \text{ and } v = r\overline{g}s.\]
A semi-Thue process is a finite set of semi-Thue productions.
If \(\Pi\) is a semi-Thue process, we write \[ u \mathop{\Rightarrow}_\Pi v\] to mean that \[u \mathop{\Rightarrow}_P v\] for some \(P\) that belongs to \(\Pi\).
We write \[ u \mathop{\Rightarrow}_\Pi^{*} v\] if there is a sequence \[u = u_1 \mathop{\Rightarrow}_\Pi u_2 \mathop{\Rightarrow}_\Pi \cdots \mathop{\Rightarrow}_\Pi u_n = v.\] The sequence \(u_1,u_2,\cdots,u_n\) is called a derivation of \(v\) from \(u\). In particular (taking \(n = 1\)), \[u \mathop{\Rightarrow}_\Pi^{*} u.\]
If the context is clear, we omit \(\Pi\) and write \(u \Rightarrow v\) and \(u \displaystyle\mathop{\Rightarrow}^{*} v\).
Let \({\cal M}\) be a nondeterministic Turing machine with alphabet \(\{s_1,\ldots,s_k\}\) and states \(q_1,\ldots,q_n\). We simulate \({\cal M}\) by a semi-Thue process \(\Sigma({\cal M})\) on the alphabet \[s_0, s_1,\ldots,s_k,q_0,q_1,\ldots,q_n,q_{n+1},h.\]
A word \(huq_ivh\), where \(0 \leq i \leq n+1\), is called a Post word if \(u\) and \(v\) are words on the subalphabet \(\{s_0,s_1,\ldots,s_k\}\).
The usual initial configuration \[ \begin{array}{ll} s_0 & u \\ \uparrow \\ q_1 \end{array} \] is encoded as the Post word \(hq_1 s_0uh\).
The following table shows the associations between quadruples of \({\cal M}\) and the productions in \(\Sigma({\cal M})\).
| quadruple of \({\cal M}\) | \(\Sigma({\cal M})\) contains |
|---|---|
| \(q_is_js_kq_l\) | \(q_is_j\rightarrow q_ls_k\) |
| \(q_is_jRq_l\) | \(\begin{array}{ll}q_is_js_k\rightarrow s_jq_ls_k, & k = 0,1,\ldots,K,\\ q_is_jh \rightarrow s_jq_ls_0h. \end{array}\) |
| \(q_is_jLq_l\) | \(\begin{array}{ll}s_kq_is_j\rightarrow q_ls_ks_j, & k = 0,1,\ldots,K,\\ hq_is_j \rightarrow hq_ls_0s_j. \end{array}\) |
In addition to the above productions, we include the following:
Whenever \(q_is_j(i=1,\ldots,n; j = 0,1,\ldots,K)\) are not the first two symbols of a quadruple of \({\cal M}\), \(\Sigma({\cal M})\) contains the production \[q_i s_j \rightarrow q_{n+1}s_j.\] Thus, \(q_{n+1}\) serves as a “halt” state.
\(\Sigma({\cal M})\) contains the productions \[\begin{array}{ll} q_{n+1}s_i \rightarrow q_{n+1}, & i = 0,1,\ldots,K, \\ q_{n+1}h \rightarrow q_0 h \\ s_i q_0 \rightarrow q_0, & i = 0, \ldots, K. \end{array}\]
Lemma A. Let \({\cal M}\) be a nondeterministic Turing machine. Then, for each string \(u\) on the alphabet of \({\cal M}\), if \[hq_1s_0uh \mathop{\Longrightarrow}_{\Sigma({\cal M})}^* z,\] then \(z\) is a Post word \(h w q_i s_j v h\) for some \(w\) and \(v\). Furthermore, if none of the words in the derivation contains \(q_0\) or \(q_{n+1}\), then there exist a sequence of configurations \(\gamma_1,\ldots, \gamma_k\) with respect to \({\cal M}\) such that \[\gamma_1 \vdash \cdots \vdash \gamma_k\] with \(\gamma_1\) being the configuration \[ \begin{array}{lll} s_0 & u \\ \uparrow \\ q_1 \end{array} \] and \(\gamma_k\) being the configuration \[ \begin{array}{lll} w & s_j & v \\ & \uparrow \\ & q_i \end{array} \]
The above lemma can be proved by induction on the length of the derivation using the definition of \(\Sigma({\cal M})\).
Theorem 2.2. Let \({\cal M}\) be a nondeterministic Turing machine. Then, for each string \(u\) on the alphabet of \({\cal M}\), \({\cal M}\) accepts \(u\) if and only if \[hq_1s_0uh \mathop{\Longrightarrow}_{\Sigma({\cal M})}^* hq_0h.\]
Proof. If \({\cal M}\) accepts \(u\), then there is an accepting sequence of configurations \(\gamma_1,\ldots, \gamma_k\). By the definition of \(\Sigma({\cal M})\) and Lemma A, there is a derivation \[ hq_1s_0uh \mathop{\Longrightarrow}_{\Sigma({\cal M})}^{*} z \] where \(z\) is a Post word \(h w q_i s_j v h\) such that no quadruple begins with \(q_i s_j\). (Note that this is possible if the production we pick for \(q_i s_j R q_l\) is \(q_i s_j s_k \rightarrow s_j q_l s_k\) if the symbol immediate to the right of the scanned square is \(s_k\) and \(q_i s_j h \rightarrow s_j q_l s_0 h\) otherwise. Similarly for \(q_i s_j L q_l\).) Then \[ z \mathop{\Longrightarrow}_{\Sigma({\cal M})} h wq_{n+1} v h \mathop{\Longrightarrow}_{\Sigma({\cal M})}^{*} h wq_{0} h \mathop{\Longrightarrow}_{\Sigma({\cal M})}^{*} h q_{0} h. \]
Conversely, suppose that \[ hq_1s_0uh \mathop{\Longrightarrow}_{\Sigma({\cal M})}^{*} h q_0 h. \] From the productions in \(\Sigma({\cal M})\), we see that there must be a Post word containing \(q_{n+1}\). Hence, there exists a derivation \[ hq_1s_0uh \mathop{\Longrightarrow}_{\Sigma({\cal M})}^{*} h w q_{n+1} v h. \] for some words \(w\) and \(v\) and no other word in the derivation contains \(q_{n+1}\) or \(q_0\). The Post word right before \(hwq_{n+1}v h\) in the derivation must be a Post word \(hw'q_{i}s_kv' h\) such that no quadruple begins with \(q_i s_k\). By Lemma A, there is a sequence of configurations \(\gamma_1,\ldots, \gamma_k\) where \(\gamma_1\) is the initial configuration \[ \begin{array}{ll} s_0 & u \\ \uparrow \\ q_1 \end{array} \] and \(\gamma_k\) is a terminal configuration. Thus, \({\cal M}\) accepts \(u\).
The inverse of the production \(g \rightarrow \bar{g}\) is the production \(\bar{g} \rightarrow g\). Let \(\Omega({\cal M})\) denote the semi-Thue process consisting of the inverses of all the productions of \(\Sigma({\cal M})\). The the following theorem follows from Theorem 2.2.
Theorem 2.3. Let \({\cal M}\) be a nondeterministic Turing machine. Then, for each string \(u\) on the alphabet of \({\cal M}\), \({\cal M}\) accepts \(u\) if and only if \[hq_0h \mathop{\Longrightarrow}_{\Omega({\cal M})}^* hq_1s_0uh.\]