Post Correspondence and Language Undecidability

For a concrete version of the effective configuration coding in [L4], tag the finite state and tape alphabets disjointly. For $C=(q,h,t)$ and any padding bound $r\ge \max (\{h\}\cup \mathrm{supp}(t))$, put $a_i:=t(i)$ and encode the padded representative as ${\tilde{C}}^{(r)}:=▹a_0\cdots a_{h-1}q{a}_h\cdots a_r,$ where $▹$ is a fresh left-end marker. This word contains exactly one state symbol and decodes unambiguously to $C$ even when some final $a_i$ are blank; different amounts of trailing blank padding may represent the same configuration. We also permit the right-blank abbreviation $▹a_0\cdots a_{h-1}q$ when $t(h)=\bigsqcup$ and every cell from $h$ onward is blank; it records the same configuration with the scanned blank left implicit. Adjoin a second fresh symbol # as a block separator. Starting with the least explicit bound for $C_0$, the intended history prefix has the form $\mathrm{\#}{\tilde{C}}_0^{(r_0)}\mathrm{\#}{\tilde{C}}_1^{(r_1)}\mathrm{\#}\cdots \mathrm{\#}{\tilde{C}}_t^{(r_t)}\mathrm{\#}\mathrm{.}$

Write a domino as $(u,v)$ with top word $u$ and bottom word $v$. Let $P_{M,w}$ contain the designated start domino $(\mathrm{\#},\mathrm{\#}{\tilde{C}}_0^{(r_0)}\mathrm{\#})\mathrm{.}$ Add copier dominoes $(c,c)$ for $c\in \mathrm{\Gamma }\cup \{▹,\mathrm{\#}\}$, but not for state symbols. For every transition $\delta (q,a)=(r,b,R)$ add $(qa,br)$. Add the boundary-padding domino $(\mathrm{\#},\bigsqcup \mathrm{\#})$: it supplies the newly scanned blank when a right move passes the last displayed tape cell, and otherwise merely permits one additional trailing blank in the next padded representative. For every $\delta (q,a)=(r,b,L)$ and $c\in \mathrm{\Gamma }$ add $(cqa,rcb)$, and add the separate clamped-left domino $(▹qa,▹rb)$. Finally, for each $c\in \mathrm{\Gamma }\cup \{▹\}$ add the accepting-cleanup dominoes $(c{q}_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{a}\mathrm{c}\mathrm{c}})$ and $(q_{\mathrm{a}\mathrm{c}\mathrm{c}}c,q_{\mathrm{a}\mathrm{c}\mathrm{c}})$, and add the terminal domino $(q_{\mathrm{a}\mathrm{c}\mathrm{c}}\mathrm{\#}\mathrm{\#},\mathrm{\#})$. These are finitely many pairs of nonempty words and are computed directly from the finite alphabet, transition table, and start configuration in [L3].

If $M$ has an accepting history $C_0,C_1,\dots ,C_t$, choose padding bounds recursively. Having chosen $r_j$, keep the same bound for $C_{j+1}$ unless a right move from cell $r_j$ requires $r_{j+1}=r_j+1$; in particular, retain a now-trailing blank when a left move erases the last nonblank cell. Begin with the start domino. For each $C_j{⊢}_M{C}_{j+1}$, use copier dominoes up to the head window, the unique right-, interior-left-, or clamped-left transition domino from step 2.1 at that window, copier dominoes after it, and then $(\mathrm{\#},\mathrm{\#})$ if $r_{j+1}=r_j$ or $(\mathrm{\#},\bigsqcup \mathrm{\#})$ if $r_{j+1}=r_j+1$. At every separator the top row has thereby copied ${\tilde{C}}_j^{(r_j)}\mathrm{\#}$ while the bottom row has appended ${\tilde{C}}_{j+1}^{(r_{j+1})}\mathrm{\#}$, so the bottom remains exactly one padded configuration block ahead. In the final accepting block, repeated whole-block passes use copiers together with $(c{q}_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{a}\mathrm{c}\mathrm{c}})$ to delete the symbol immediately left of the accepting state, or with $(q_{\mathrm{a}\mathrm{c}\mathrm{c}}c,q_{\mathrm{a}\mathrm{c}\mathrm{c}})$ to delete the symbol immediately right of it. These passes eventually leave the one-block lag $q_{\mathrm{a}\mathrm{c}\mathrm{c}}\mathrm{\#}$, which the terminal domino closes because its top is $q_{\mathrm{a}\mathrm{c}\mathrm{c}}\mathrm{\#}\mathrm{\#}$ and its bottom is #. The two full concatenations are then equal, giving a modified-PCP match.

Conversely, let a modified-PCP match be given. Its first domino is the designated start domino by [L1], so the unmatched bottom suffix initially is exactly ${\tilde{C}}_0^{(r_0)}\mathrm{\#}$. Induct over the separators subsequently matched by the top row. Copier dominoes cannot copy a state symbol. Before $q_{\mathrm{a}\mathrm{c}\mathrm{c}}$ appears, the unique state symbol in the current block must therefore be consumed by one transition domino from step 2.1. The symbol immediately before it distinguishes an interior left move from the special $▹$-boundary move. All other tape symbols are copied, while the choice between $(\mathrm{\#},\mathrm{\#})$ and $(\mathrm{\#},\bigsqcup \mathrm{\#})$ either preserves the displayed length or adds one trailing blank. If a right move has put a nonaccepting state just beyond the last displayed cell, choosing $(\mathrm{\#},\mathrm{\#})$ would leave that state immediately before the separator, where no transition or cleanup top can consume it, so a complete match must choose the boundary-padding tile. If the new state is $q_{\mathrm{a}\mathrm{c}\mathrm{c}}$, the shorter choice is precisely the right-blank abbreviation from step 1.1. Consequently every pre-cleanup bottom block decodes to the unique configuration $C_{j+1}$ with $C_j{⊢}_M{C}_{j+1}$, although its harmless trailing-blank padding need not be unique. Cleanup dominoes contain $q_{\mathrm{a}\mathrm{c}\mathrm{c}}$ and cannot begin this suffix before an accepting block has been reached; after they begin, their shorter bottom words and the terminal anchor can remove the remaining offset. Hence every match has a prefix decoding to an accepting computation history of the original machine $M$ on $w$.

Steps 3.1 and 3.2 prove that $P_{M,w}$ has a match if and only if $M$ has an accepting computation history on $w$. Step 2.1 constructs its finite domino list effectively from $(M,w)$.

Define a map $f$ on coded machine-input pairs by $f(⟨M,w⟩):=P_{M,w}\mathrm{.}$ By [L1], this map is total and computable and satisfies $⟨M,w⟩\in A_{TM}⟺f(⟨M,w⟩)\in \mathrm{MPCP}\mathrm{.}$ Thus $A_{TM}{\le }_m\mathrm{MPCP}$.

If modified PCP were decidable, then [L3] and step 1.1 would imply that $A_{TM}$ is decidable. This contradicts [L2].

Therefore modified PCP is undecidable.

Introduce fresh symbols * and !. For a word $a_1\cdots a_k$, write $L(a_1\cdots a_k):=a_1\ast a_2\ast \cdots a_k\ast ,R(a_1\cdots a_k):=\ast a_1\ast a_2\ast \cdots \ast a_k\mathrm{.}$ Construct a PCP instance consisting of one special start tile, one shifted tile for each original domino, and one end tile: $(\ast L(x_1),R(y_1)),(L(x_i),R(y_i))(1\le i\le n),(!,\ast !)\mathrm{.}$ The extra leading * appears only on the special start tile, and ! appears only on the end tile.

If $1=i_1,i_2,\dots ,i_k$ is a modified-PCP match, choose the special start tile, then the ordinary shifted tiles for $i_2,\dots ,i_k$, and finally the end tile. The top concatenation is $\ast L(x_1)L(x_{i_2})\cdots L(x_{i_k})!,$ while the bottom concatenation is $R(y_1)R(y_{i_2})\cdots R(y_{i_k})\ast !\mathrm{.}$ Because the original match satisfies $x_1{x}_{i_2}\cdots x_{i_k}=y_1{y}_{i_2}\cdots y_{i_k}$, these two shifted strings agree symbol by symbol: the leading * on top supplies the one-symbol offset, every interior * matches the next boundary marker on the bottom, and the end tile matches the final extra *. Hence the transformed PCP instance has a match.

Conversely, let a PCP match be given for the transformed instance. The common concatenated word begins with *, and among the available top words only the special start tile begins with *, so the first chosen tile is the special start tile. Equality cannot be completed without an end tile. Consider the prefix ending at the first use of that tile. The fresh symbol ! occurs nowhere else, so its two first occurrences align and this prefix already has equal top and bottom concatenations. Delete the initial *, the terminal !, and all separator symbols * from this matched prefix. The remaining equality is $x_1{x}_{i_2}\cdots x_{i_k}=y_1{y}_{i_2}\cdots y_{i_k}\mathrm{.}$ Thus the recovered sequence begins with the original first domino and is a modified-PCP match. Later repetitions of the start or end tiles, if present in the original PCP match, are irrelevant because the first completed prefix has already supplied the required modified-PCP match.

Steps 2.1 and 2.2 prove the required equivalence, and the construction in step 1.1 is effective. Therefore modified PCP many-one reduces to PCP.

By [L1], there is a total computable map sending each modified-PCP instance to a PCP instance with the same yes-or-no answer.

If PCP were decidable, then [L3] and step 1.1 would imply that modified PCP is decidable. This contradicts [L2].

Therefore PCP is undecidable.

Enumerate all nonempty finite sequences over $\{1,\dots ,n\}$ in length-lexicographic order: $(1),(2),\dots ,(n),(1,1),(1,2),\dots \mathrm{.}$ For each sequence $\sigma =(i_1,\dots ,i_k)$, compute the two concatenations $u_{i_1}\cdots u_{i_k}$ and $v_{i_1}\cdots v_{i_k}$ and compare them.

If the instance has a match, [L1] supplies some witnessing sequence $\sigma$, and the enumeration from step 1.1 eventually reaches it and accepts. If the instance has no match, every tested sequence fails and the search runs forever.

Therefore there is a Turing machine that accepts exactly the PCP yes-instances, so PCP is recognizable.

From the PCP instance build two context-free grammars over the alphabet consisting of the original symbols together with index symbols $1,\dots ,n$: $S_T\to u_i{S}_{T}i\mid u_{i}i,S_B\to v_i{S}_{B}i\mid v_{i}i(1\le i\le n)\mathrm{.}$ Thus $G_T$ generates exactly the words $u_{i_1}\cdots u_{i_k}{i}_k\cdots i_1$, and $G_B$ generates exactly the words $v_{i_1}\cdots v_{i_k}{i}_k\cdots i_1$, for nonempty index sequences $i_1,\dots ,i_k$.

If $i_1,\dots ,i_k$ is a PCP match, then $u_{i_1}\cdots u_{i_k}{i}_k\cdots i_1=v_{i_1}\cdots v_{i_k}{i}_k\cdots i_1,$ so that common word lies in $L(G_T)\cap L(G_B)$. Conversely, if a word lies in $L(G_T)\cap L(G_B)$, its reversed index suffix uniquely determines the same index sequence on both sides, and removing that suffix leaves $u_{i_1}\cdots u_{i_k}=v_{i_1}\cdots v_{i_k}\mathrm{.}$ Hence the original PCP instance has a match if and only if $L(G_T)\cap L(G_B)\mathrm{\ne }\mathrm{\varnothing }$.

The map from the PCP instance to the pair $(G_T,G_B)$ is total and computable by step 1.1. If intersection-emptiness for pairs of CFGs were decidable, step 2.1 and [L3] would make PCP decidable, contradicting [L2].

Therefore emptiness of the intersection of two CFGs is undecidable.

Choose the explicit finite configuration alphabet allowed by [L2], and encode a candidate history as $C_0\mathrm{\#}{C}_1^R\mathrm{\#}{C}_2\mathrm{\#}{C}_3^R\mathrm{\#}\cdots ,$ alternating ordinary and reversed configuration words. Let $B_{M,w}$ be the set of words that are not accepting histories in this encoding. Malformed words and words with the wrong initial or accepting endpoint form regular languages. For an alleged adjacent pair $C_i,C_{i+1}$, a pushdown automaton nondeterministically chooses that pair, pushes the first configuration, and compares it with the oppositely oriented second configuration while allowing exactly one of the finitely many local windows prescribed by a transition of $M$. It accepts when no legal window explains the pair. Taking separate machines for the two parities and their finite union handles every adjacent pair. Thus histories containing an illegal transition form a context-free language, and so does their union with the two regular error languages. The construction is effective in the finite transition table, hence produces a CFG $G_{M,w}$ with $L(G_{M,w})=B_{M,w}$.

By the definition of $B_{M,w}$, the grammar $G_{M,w}$ is universal exactly when there is no accepting computation history of $M$ on $w$. Using [L1], this is equivalent to $L(G_{M,w})={\mathrm{\Sigma }}^{\ast }⟺⟨M,w⟩\mathrm{\notin }{A}_{TM}\mathrm{.}$

The construction of $G_{M,w}$ is effective by step 1.1. If CFG universality were decidable, then step 2.1 would decide $\overline{A_{TM}}$, and hence decide $A_{TM}$ by complementing the answer. That contradicts [L3].

Therefore CFG universality is undecidable.

Let $U_{\mathrm{\Sigma }}$ be a fixed grammar generating ${\mathrm{\Sigma }}^{\ast }$. Such a grammar is easy to write, for example with productions $S\to aS\mid \epsilon (a\in \mathrm{\Sigma })\mathrm{.}$ Then $L(G)={\mathrm{\Sigma }}^{\ast }⟺L(G)=L(U_{\mathrm{\Sigma }})\mathrm{.}$

Therefore a decision procedure for CFG equivalence would decide whether $L(G)={\mathrm{\Sigma }}^{\ast }$ by comparing $G$ with the fixed universal grammar $U_{\mathrm{\Sigma }}$. That would decide CFG universality, contradicting [L2].

Hence CFG equivalence is undecidable.

Choose fresh terminal symbols ${\iota }_1,\dots ,{\iota }_n$ disjoint from the PCP alphabet, and build one grammar with start symbol $S$ and two branches: $S\to T\mid B,$ $T\to u_{i}T{\iota }_i\mid u_i{\iota }_i,B\to v_{i}B{\iota }_i\mid v_i{\iota }_i(1\le i\le n)\mathrm{.}$ A leftmost derivation from $T$ yields exactly the words $u_{i_1}\cdots u_{i_k}{\iota }_{i_k}\cdots {\iota }_{i_1}$, and a derivation from $B$ yields the analogous words with the $v_i$. The fresh reversed suffix uniquely determines the entire index sequence, so each branch is unambiguous.

If $i_1,\dots ,i_k$ is a PCP match, then the word $u_{i_1}\cdots u_{i_k}{\iota }_{i_k}\cdots {\iota }_{i_1}=v_{i_1}\cdots v_{i_k}{\iota }_{i_k}\cdots {\iota }_{i_1}$ has one leftmost derivation beginning with $S\Rightarrow T$ and another beginning with $S\Rightarrow B$. Hence the grammar is ambiguous by [L1].

Conversely, if the grammar is ambiguous, [L1] gives a word with two distinct leftmost derivations. Step 1.1 proves that neither the $T$ branch nor the $B$ branch has two derivations of one word, so one derivation begins with $S\Rightarrow T$ and the other with $S\Rightarrow B$. The common terminal word has the form $u_{i_1}\cdots u_{i_k}{\iota }_{i_k}\cdots {\iota }_{i_1}=v_{j_1}\cdots v_{j_m}{\iota }_{j_m}\cdots {\iota }_{j_1}\mathrm{.}$ Freshness and unique parsing of the reversed suffix force $k=m$ and $i_r=j_r$ for every $r$, so $i_1,\dots ,i_k$ is a PCP match.

Steps 2.1 and 2.2 show that the constructed grammar is ambiguous if and only if the original PCP instance has a match. If CFG ambiguity were decidable, then [L4] and this equivalence would make PCP decidable, contradicting [L3].

Therefore CFG ambiguity is undecidable.

If a language is regular, choose a DFA $D$ recognizing it. Make one CFG whose variables are the states of $D$, whose start variable is the start state, whose productions are $q\to a\delta (q,a)$ for each transition, and whose accepting states also have productions $q\to \epsilon$. Then the grammar generates exactly the words accepted by $D$. Hence every regular language is context-free.

Every decidable language is recognizable by running its decider and accepting exactly when the decider accepts. Thus $\text{decidable}\subseteq \text{computably enumerable}\mathrm{.}$

The language $L_{ab}:=\{a^n{b}^n:n\ge 0\}$ is context-free, for example via the grammar $S\to aSb\mid \epsilon$. It is not regular: if it were regular, [L1] would give a pumping length $p$, but $a^p{b}^p$ cannot be pumped inside the first $p$ symbols without changing the number of $a$'s and leaving the number of $b$'s fixed. Therefore $\text{regular}⊊\text{context-free}\mathrm{.}$

Relabel the binary alphabet of $A_{TM}$ injectively by the two chosen symbols $a,b\in \mathrm{\Sigma }$. This computable letter-by-letter bijection preserves recognizability and decidability. By [L5] and [L6], the relabeled language over $\mathrm{\Sigma }$ is computably enumerable but not decidable. Therefore $\text{decidable}⊊\text{computably enumerable}\mathrm{.}$

Every context-free language is decidable by [L2], so $\text{context-free}\subseteq \text{decidable}\mathrm{.}$

The language $L_{aba}:=\{a^n{b}^n{a}^n:n\ge 0\}$ is decidable by checking the three blocks and comparing their lengths. It is not context-free: if $p$ were a pumping length from [L3], then a pumping window of length at most $p$ in $a^p{b}^p{a}^p$ could meet at most two consecutive blocks and could not meet both $a$-blocks. Pumping a nonempty part therefore changes at least one of the three required counts without changing all three equally, or destroys the block order. This contradicts [L3]. Hence $\text{context-free}⊊\text{decidable}\mathrm{.}$

Steps 2.1, 4.1, and 2.2 prove that all three containments are strict over the fixed alphabet $\mathrm{\Sigma }$.

If one were allowed to reorder symbols inside the domino, the unique tile could be changed from $(ab,ba)$ to $(ab,ab)$ by swapping the bottom symbols, and then a one-tile sequence would look like a match.

In actual PCP, [L1] forbids that operation. The only nonempty sequences use the same domino some number $k\ge 1$ of times, yielding top word $(ab{)}^k$ and bottom word $(ba{)}^k$. Their first symbols are always different, so these words are never equal.

Therefore the claimed permission is false: PCP concatenates whole dominoes in the chosen order and does not allow symbol reordering within a tile.

Fact [L1] says that for any fixed word $w$, one can decide separately whether $w\in L(G)$ and whether $w\in L(H)$. That is a pointwise membership statement about the two languages themselves.

The claim in the statement is stronger: it asks for one algorithm that, from the grammar descriptions alone, decides whether some word lies in both languages. But [L2] says that this description-level problem is undecidable.

Hence the statement is false. Decidable membership for each individual CFL does not make the intersection-emptiness problem for pairs of CFGs decidable.