Problem Solving in Automata, Languages, and Complexity

272 COMPUTABUJTY THEORY

POST CORRESPONDENCE PROBLEM (PCP): Given a finite set of

ordered pairs (~1, ~1) ,... , (zn, yn) of strings over C, determine

whether there is a finite sequence of integers (il , iz,... , im), with

each ij E { 1,... , n}, such that

For a particular instance {(xl, yl),... , (x,, yn)) of the problem PCP, if

there exists a sequence (il, i2,... , im) satisfying (5.4), then we say the string

XilXiZ l l ’ xi, is a s&&on to this instance.

An easy way to understand the problem PCP is to treat each pair (xi, yi>

as a domino with string xi at the top and string yi at the bottom: xi

R

. The
Yi
question here then is to select, from the given dominoes

my El, ‘** > El,

with unlimited supply for each type, some dominoes and arrange them into a

row so that the top part of the dominoes spells the same word as the bottom

part of the dominoes. For instance, we can obtain a solution baaaau from the

following given dominoes

as follows:

* Example 5.45 Prove that the problem PCP is undeciduble (with respect to

some ulphubet C).

Pro05 Let M be a fixed DTM, with a one-way tupe (i.e., the original one-tape

DTM defined in Section 4.1) such that the problem of determining whether AI

halts on a given string x E (0, 1}* is undecidable. (Le., L(M) is a nonrecursive

set.) We construct a reduction from the halting problem of this fixed DTM

AI to the problem PCP. That is, for each string x, we need to produce an

instance p3$ = {(xl, yl),... , (x,, y,,-J} such that IV halts on x if and only if

P, has a solution x.

Assume that the set of states in AI is & = {al, q2,... , qn}, where q1 is the

initial state and qn is the halting state, and that the set of tape symbols of M

is I? = {%S2,.“, sk}. Also assume that Qnr = 0. Let Q’ = {&,&,.. .,(m}

and I?’ = {Sl, S2,... , ~lc). Then, we fix the alphabet of our PCP problem as

The pairs of strings in Px consists of the following groups (for the sake of

clarity, we show them as dominoes) :