The Undecidability of Post's Correspondence Problem
Applications of Post's Correspondence Problem
The Post's Correspondence Problem, or PCP for short, consists of the following domain and question.
with infinitely many cards in each pile, can one draw a sequence of n 1 cards
from these piles, so that the string x_{i1} x_{in} formed on the top of the cards will equal the string y_{i1} y_{in} formed on the bottom?
The tuple (i_{1}, i_{2}, i_{3}, i_{4}, i_{5}, i_{6}) = (1, 3, 2, 4, 4, 3) is a witness for a positive solution because x_{1}x_{3}x_{2}x_{4}x_{4}x_{3} = y_{1}y_{3}y_{2}y_{4}y_{4}y_{3} = 01111001011111. The positive solution has also the witnesses (1, 3, 2, 4, 4, 3, 1, 3, 2, 4, 4, 3), (1, 3, 2, 4, 4,3,1,3,2,4,4,3,1,3,2, 4, 4, 3), etc. On the other hand, the PCP has the solution no for <(0, 10), (01, 1)>.
The Undecidability of Post's Correspondence Problem
Post's correspondence problem is very useful for showing the undecidability of many other problems by means of reducibility. Its undecidability follows from its capacity for simulating the computations of Turing machines, as exhibited indirectly in the following proof through derivations in Type 0 grammars.
Theorem 4.7.1 The PCP is an undecidable problem.
Proof By Corollary 4.6.1 the membership problem is undecidable for Type 0 grammars. Thus, it is sufficient to show how from each instance (G, w) of the membership problem for Type 0 grammars, an instance I can be constructed, such that the PCP has a positive solution at I if and only if w is in L(G).
For the purpose of the proof consider any Type 0 grammar G = <N, , P, S> and any string w in *. With no loss of generality assume that #, ¢, and $ are new symbols not in N . Then let the corresponding instance I = <(x_{1}, y_{1}), . . . , (x_{k}, y_{k})> of PCP be of the following form.
PCP has a positive solution at I if and only if I can trace a derivation that starts at S and ends at w.
For each derivation in G of the form S _{1} _{m} w, the instance I has a witness (i_{1}, . . . , i_{n}) of a positive solution such that either
or
depending on whether m is even or odd, respectively.
On the other hand, each witness (i_{1}, . . . , i_{n}) of a positive solution for PCP at I has a smallest integer t 1 such that x_{i1} x_{it} = y_{i1} y_{it}. In such a case, x_{i1} x_{it} = y_{i1} y_{it} = ¢S#_{2}#_{4} _{m} for some derivation S * _{1} * _{2} * * _{m} * w.
The instance I consists of pairs of the following form
The other pairs are used to force the tracing to go from each given sentential form to a sentential form ', such that * '. The tracing is possible because each of the pairs (x_{i}, y_{i}) is defined so that y_{i} provides a "window" into , whereas x_{i} provides an appropriate replacement for y_{i} in '.
The pairs of the form (X, ) and (, X) in (c) are used for copying substrings from to '. The pairs of the form (, ) and (, ), , in (d) are used for replacing substrings in by substrings in '. The pairs of the form (X, ) and (, X) in (e) are used for replacing substrings in by the empty string in '.
The window is provided because for each 1 i_{1}, . . . , i_{j} k, the strings x = x_{i1} x_{ij} and y = y_{i1} y_{ij} satisfy the following properties.
Example 4.7.2 If G is a grammar whose set of production rules is {S aSaSaS, aS }, then the instance of the PCP that corresponds to (G, ) as determined by the proof of Theorem 4.7.1, is <(¢S, ¢), (, S), (aSaSaS, ), (, #aS), (#, ), (, aaS), (a, ), (, SaS), (S, ), (#, ), (, #), (a, ), (, a), (S, ), (, S), ($, $)>.
The instance has a positive solution with a witness that corresponds to the arrangement in Figure 4.7.1.

Applications of Post's Correspondence Problem
The following corollary exhibits how Post's correspondence problem can be used to show the undecidability of some other problems by means of reducibility.
Corollary 4.7.1 The equivalence problem is undecidable for finitestate transducers.
Proof Consider any instance <(x_{1}, y_{1}), . . . , (x_{k}, y_{k})> of PCP. Let be the minimal alphabet such that x_{1}, . . . , x_{k}, y_{1}, . . . , y_{k} are all in *. With no loss of generality assume that = {1, . . . , k} is an alphabet.
Let M_{1} = <Q_{1}, , , _{1}, q_{0}, F_{1}> be a finitestate transducer that computes the relation * × *, that is, a finitestate transducer that accepts all inputs over , and on each such input can output any string over .
Let M_{2} = <Q_{2}, , , _{2}, q_{0}, F_{2}> be a finitestate transducer that on input i_{1} i_{n} outputs some w such that either w x_{i1} x_{in} or w y_{i1} y_{in}. Thus, M_{2} on input i_{1} i_{n} can output any string in * if x_{i1} x_{in} y_{i1} y_{in}. On the other hand, if x_{i1} x_{in} = y_{i1} y_{in}, then M_{2} on such an input i_{1} i_{n} can output any string in *, except for x_{i1} x_{in}.
It follows that M_{1} is equivalent to M_{2} if and only if the PCP has a negative answer at the given instance <(x_{1}, y_{1}), . . . , (x_{k}, y_{k})>.
Example 4.7.3 Consider the instance <(x_{1}, y_{1}), (x_{2}, y_{2})> = <(0, 10), (01, 1)> of PCP. Using the terminology in the proof of Corollary 4.7.1, = {0, 1} and = {1, 2}. The finitestate transducer M_{1} can be as in Figure 4.7.2(a),

M_{2} on a given input i_{1} i_{n} nondeterministically chooses between its components M_{x} and M_{y}. In M_{x} it outputs a prefix of x_{i1} x_{in}, and in M_{y} it outputs a prefix of y_{i1} y_{in}. Then M_{2} nondeterministically switches to M_{>}, M_{<}, or M_{}.
M_{2} switches from M_{x} to M_{>} to obtain an output that has x_{i1} x_{in} as a proper prefix. M_{2} switches from M_{x} to M_{<} to obtain an output that is proper prefix of x_{i1} x_{in}. M_{2} switches from M_{x} to M_{} to obtain an output that differs from x_{i1} x_{in} within the first x_{i1} x_{in} symbols.
M_{2} switches from M_{y} to M_{>}, M_{<}, M_{} for similar reasons, respectively.
The following corollary has a proof similar to that given for the previous one.
Corollary 4.7.2 The equivalence problem is undecidable for pushdown automata.
Proof Consider any instance <(x_{1}, y_{1}), . . . , (x_{k}, y_{k})> of PCP. Let _{1} be the minimal alphabet such that x_{1}, . . . , x_{k}, y_{1}, . . . , y_{k} are all in _{1}*. With no loss of generality assume that _{2} = {1, . . . , k} is an alphabet, that _{1} and _{2} are mutually disjoint, and that Z_{0} is a new symbol not in _{1}.
Let M_{1} = <Q_{1}, _{1} _{2}, _{1} Z_{0}, _{1}, q_{0}, Z_{0}, F_{1}> be a pushdown automaton that accepts all the strings in (_{1} _{2})*. (In fact, M_{1} can also be a finitestate automaton.)
Let M_{2} = <Q_{2}, _{1} _{2}, _{1} Z_{0}, _{2}, q_{0}, Z_{0}, F_{2}> be a pushdown automaton that accepts an input w if and only if it is of the form i_{n} i_{1}u, for some i_{1} i_{n} in _{1}* and some u in _{2}*, such that either u x_{i1} x_{in} or u y_{i1} y_{in}.
It follows that M_{1} and M_{2} are equivalent if and only if the PCP has a negative answer at the given instance.
The pushdown automaton M_{2} in the proof of Corollary 4.7.2 can be constructed to halt on a given input if and only if it accepts the input. The constructed pushdown automaton halts on all inputs if and only if the PCP has a negative solution at the given instance. Hence, the following corollary is also implied from the undecidability of PCP.
Corollary 4.7.3 The uniform halting problem is undecidable for pushdown automata.
PCP is a partially decidable problem because given an instance <(x_{1}, y_{1}), . . . , (x_{k}, y_{k})> of the problem one can search exhaustively for a witness of a positive solution, for example, in {1, . . . , k}* in canonical order. With such an algorithm a witness will eventually be found if the instance has a positive solution. Alternatively, if the instance has a negative solution, then the search will never terminate.