4.7  Post's Correspondence Problem

      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.

Domain:

{ <(x₁, y₁), . . . , (x_k, y_k)> | k 1 and x₁, . . . , x_k, y₁, . . . , y_k are strings over some alphabet. }

Question:

Are there an integer n 1 and indices i₁, . . . , i_n for the given instance <(x₁, y₁), . . . , (x_k, y_k)> such that x_i1 x_in = y_i1 y_in? Each sequence i₁, . . . , i_n that provides a yes answer is said to be a witness for a positive solution to the given instance of PCP.

Domain:

{ | k 1, and each is a domino card with the string x_i on its top and the string y_i on its bottom, 1 i k. }

Question:

Given k 1 piles of cards

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₁, i₂, i₃, i₄, i₅, i₆) = (1, 3, 2, 4, 4, 3) is a witness for a positive solution because x₁x₃x₂x₄x₄x₃ = y₁y₃y₂y₄y₄y₃ = 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₁, y₁), . . . , (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₁, . . . , 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₁, . . . , 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#₂#_{4 m} for some derivation S * ₁ * ₂ * * _m * w.

The instance I consists of pairs of the following form

1.  A pair of the form (˘S, ˘).
2.  A pair of the form ($, $).
3.  A pair of the form (X, ), and a pair of the form (, X), for each symbol X in N {#}.
4.  A pair of the form (, ), and a pair of the form (, ), for each production rule in G that satisfies .
5.  A pair of the form (X, ), and a pair of the form (, X), for each production rule in G and for each X in N {#}.

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₁, . . . , i_j k, the strings x = x_i1 x_ij and y = y_i1 y_ij satisfy the following properties.

1.  If x is a prefix of y, then x = y. Otherwise there would have been a least l such that x_i1 x_il is a proper prefix of y_i1 y_il. In which case (x_il, y_il) would be equal to (v, uvv') for some nonempty strings v and v'. However, by definition, no pair of such a form exists in I.
2.  If y is a proper prefix of x, then the sum of the number of appearances of the symbols # and in x is equal to one plus the sum of the number of appearances of # and in y. Otherwise, there would be a least l > 1 for which x_i1 x_il and y_i1 y_il do not satisfy the property. In such a case, because of the minimality of l, x_il and y_il would have to differ in the number of # and they contain. That is, by definition of I, (x_il, y_il) would have to equal either ($, $) or (˘, ˘). However, ($, ) is an impossible choice because it implies that x_i1 x_il = y_i1 y_il, and (˘, ˘) is an impossible choice because it implies that x_i1 x_il-1 = y_i1 y_il-1 (and hence that the property holds).

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.

Figure 4.7.1 An arrangement of PCP cards for describing a derivation for , in the grammar that consists of the production rules S aSaSaS and aS .

 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 finite-state transducers.

Proof     Consider any instance <(x₁, y₁), . . . , (x_k, y_k)> of PCP. Let be the minimal alphabet such that x₁, . . . , x_k, y₁, . . . , y_k are all in *. With no loss of generality assume that = {1, . . . , k} is an alphabet.

Let M₁ = <Q₁, , , ₁, q₀, F₁> be a finite-state transducer that computes the relation * × *, that is, a finite-state transducer that accepts all inputs over , and on each such input can output any string over .

Let M₂ = <Q₂, , , ₂, q₀, F₂> be a finite-state transducer that on input i₁ i_n outputs some w such that either w x_i1 x_in or w y_i1 y_in. Thus, M₂ on input i₁ 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₂ on such an input i₁ i_n can output any string in *, except for x_i1 x_in.

It follows that M₁ is equivalent to M₂ if and only if the PCP has a negative answer at the given instance <(x₁, y₁), . . . , (x_k, y_k)>.

Example 4.7.3    Consider the instance <(x₁, y₁), (x₂, y₂)> = <(0, 10), (01, 1)> of PCP. Using the terminology in the proof of Corollary 4.7.1, = {0, 1} and = {1, 2}. The finite-state transducer M₁ can be as in Figure 4.7.2(a),

Figure 4.7.2 The finite-state transducer in (a) is equivalent to the finite-state transducer in (b) if and only if the PCP has a positive solution at <(0, 10), (01, 1)>.

M₂ on a given input i₁ 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₂ nondeterministically switches to M_>, M_<, or M.

M₂ switches from M_x to M_> to obtain an output that has x_i1 x_in as a proper prefix. M₂ switches from M_x to M_< to obtain an output that is proper prefix of x_i1 x_in. M₂ 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₂ 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₁, y₁), . . . , (x_k, y_k)> of PCP. Let ₁ be the minimal alphabet such that x₁, . . . , x_k, y₁, . . . , y_k are all in ₁*. With no loss of generality assume that ₂ = {1, . . . , k} is an alphabet, that ₁ and ₂ are mutually disjoint, and that Z₀ is a new symbol not in ₁.

Let M₁ = <Q₁, _{1 2}, ₁ Z₀, ₁, q₀, Z₀, F₁> be a pushdown automaton that accepts all the strings in (_{1 2})*. (In fact, M₁ can also be a finite-state automaton.)

Let M₂ = <Q₂, _{1 2}, ₁ Z₀, ₂, q₀, Z₀, F₂> be a pushdown automaton that accepts an input w if and only if it is of the form i_n i₁u, for some i₁ i_n in ₁* and some u in ₂*, such that either u x_i1 x_in or u y_i1 y_in.

It follows that M₁ and M₂ are equivalent if and only if the PCP has a negative answer at the given instance.

The pushdown automaton M₂ 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₁, y₁), . . . , (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.

[next] [front] [up]