The Post Correspondence Problem
Prakash Panangaden 23rd March 2021
We are given a finite set of pairs of strings over some alphabet Σ: S = {(α1, β1), (α2, β2), . . . (αk, βk)}.
We represent these strings as dominos; little tiles with one string on top and another string on the bottom as in this example:
b babbb ba bbb , ba , a
We assume we have as many copies as want of each type of tile; we can represent this solution as a sequence of natural numbers. A description of the tiles is called an instance of the Post correspondence problem (PCP). Solving the problem means finding a sequence of tiles (with repetitions if we want) so that when we read the concatenated string on the top of the tiles it is the same as the concatenated string at the bottom of the tiles.
The example of PCP given above has the solution 2113 because we have
babbb b b ba = babbbbbba 2113
ba bbb bbb a = babbbbbba
We say that the above instance of PCP has a solution or is solvable. A PCP may have many nontrivial solutions or none. For example, the follow- ing
ab b a abb, ba, bb
has no solution because the strings on top are all strictly shorter than the strings below.
1
Theorem 1 (Post). It is undecidable whether a given Post system has a solution.
Proof . Given a Turing machine M and a word w, we give an effective construction of a PCP such that, the solution to the PCP given a valid computation for M run with w as input. This VALCOMPS(M,w) = ∅ if and only if the PCP instance has no solution.
We design the domino tiles so that in a match each tile links a configuration of M with the next configuration. We use # as a special separator symbol. As usual we represent configurations as w1qw2 where w1 is the word to the left of the read head of M, q is the state of M and w2 is the word that starts with the symbol on the cell that the read head is looking at and continues to the right on the tape.
We make a temporary restriction on PCP: we insist that there is a special designated tile called the start tile and every solution is required to start with this tile. Later we will eliminate this restriction.
We insist that the starting tile is #
#q0w0 …wn
where q0 is the start state of M and the word w consists of the symbols
w0 …wn.
For every transition of the form δ(q,a) = (r,b,R) with q not equal to the
reject state we make a tile of the form
qa br
For every transition of the form δ(q,a) = (r,b,L) with q not equal to the reject state we make a tile of the form
cqa rcb
for every c ∈ Σ.
For every a ∈ Γ we create a tile of the form
a. a
2
Weadd#and# . ##
Finally we add three more tiles
aqa qaa qa##
q,q,#. aa
The tiles force one to construct a valid computation. Suppose that Γ = {0,1,2, } and w = 0100 and δ(q0,0) = (q7,2,R). We start with the start
tile
# #q0 0100#
and to continue the match we have to use a tile that starts with q00 on top so doing this and then adding tiles to complete the extra letters we get
# q00100#
#q00100# 2q7 1 0 0 #
as you can see the top is now matched but the bottom has extra symbols that exactly correspond to the next configuration. The last few tiles are used to finish up the computation as follows.
Suppose that M enters an accept state so the tiles are now aligned as follows (for example):
# #21qa 02# .
aqa qaa q,q
to catch up and to finish the computation we use
We use the tiles
as follows
qa## #
# qa## #qa# # .
aa
The last detail is generalizing the modified version of the Post correspon- dence problem to the original version. We suppose that ∗ and Q are sym- bols that we have never used before. If u = u0 . . . un is a string, we define ∗u := ∗u0 ∗…∗un and u∗ := u0 ∗…un∗ and ∗u∗ = ∗u0 ∗…∗un∗. For
3
every tile t in our original set of tiles we add ∗t and for the start tile b b∗
t0 we add ∗t0 ; we have to start with this tile otherwise no match is b0 ∗b0∗
possible. Finally, to end we add the tile ∗Q. Q
So we have effectively constructed a set of tiles with the property that there is a solution if and only if M accepts w. This is thus, even a mapping reduction. If PCP were solvable we could solve the acceptance problem for Turing machines which is known to be undecidable.
4