Post Correspondence and Language Undecidability: Examples and Counterexamples

Choose the three displayed dominoes in order. Their top concatenation is $\mathrm{\#}▹q_{0}1\mathrm{\#},$ while their bottom concatenation is $\mathrm{\#}▹q_{0}1\mathrm{\#}▹q_{\mathrm{a}\mathrm{c}\mathrm{c}}1\mathrm{\#}\mathrm{.}$ Thus the top has matched the initial block and the bottom is exactly one block ahead with the accepting configuration. No right-boundary extension is needed because the only move is the clamped left move.

After the three dominoes in step 1.1, append $(▹q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{a}\mathrm{c}\mathrm{c}}),(1,1),(\mathrm{\#},\mathrm{\#}),(q_{\mathrm{a}\mathrm{c}\mathrm{c}}1,q_{\mathrm{a}\mathrm{c}\mathrm{c}}),(\mathrm{\#},\mathrm{\#}),(q_{\mathrm{a}\mathrm{c}\mathrm{c}}\mathrm{\#}\mathrm{\#},\mathrm{\#})\mathrm{.}$ Every pair belongs to the construction in [L1], and the two complete rows are both $\mathrm{\#}▹q_{0}1\mathrm{\#}▹q_{\mathrm{a}\mathrm{c}\mathrm{c}}1\mathrm{\#}{q}_{\mathrm{a}\mathrm{c}\mathrm{c}}1\mathrm{\#}{q}_{\mathrm{a}\mathrm{c}\mathrm{c}}\mathrm{\#}\mathrm{\#}\mathrm{.}$ Thus this instance has a match. Conversely, [L1] decodes every match back to an accepting history; here determinism leaves only $C_0,C_1$. The theorem The modified Post correspondence problem is undecidable says that no algorithm can decide all such instances, even though this particular accepting instance is visible directly.

The language $L_{ab}$ is context-free via the grammar $S\to aSb\mid \epsilon$. If it were regular, [L2] would give a pumping length $p$, but pumping the word $a^p{b}^p$ inside its first $p$ symbols changes only the number of $a$'s. So $L_{ab}$ witnesses $\text{regular}⊊\text{context-free}\mathrm{.}$

The language $L_{abc}$ is decidable by a machine that first checks the form $a^{\ast }{b}^{\ast }{c}^{\ast }$ and then counts the three block lengths and compares them. If it were context-free, [L3] would give a pumping length $p$ for the word $a^p{b}^p{c}^p$, but any factor $vwx$ with $\mathrm{\mid }vwx\mathrm{\mid }\le p$ lies in at most two consecutive blocks, so pumping $v$ and $x$ changes at most two symbol counts and destroys equality of all three counts. Thus $L_{abc}$ witnesses $\text{context-free}⊊\text{decidable}\mathrm{.}$

By [L4] and [L5], $A_{TM}$ is computably enumerable but not decidable. So it witnesses $\text{decidable}⊊\text{computably enumerable}\mathrm{.}$

These are exactly the three strict containments proved in [L1]. The point of the example is that one should keep the witnesses separate rather than expecting one language to witness every gap at once.

Consider the one-domino instance $(ab,ba)\mathrm{.}$ If internal permutation were allowed, the bottom word ba could be rearranged to ab, so one use of the domino would look like a match.

In actual PCP, only whole dominoes may be concatenated. Using the unique tile $k\ge 1$ times gives top word $(ab{)}^k$ and bottom word $(ba{)}^k$, whose first symbols differ. So the instance has no legal match.

Therefore this instance refutes the statement. It is exactly the concrete counterexample recorded abstractly in [L1].