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
bbb
]
,
[
babbb
ba
]
,
[
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
2 1 1 3
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
abb
]
,
[
b
ba
]
,
[ a
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
We add
[
#
#
]
and
[
#
#
]
.
Finally we add three more tiles[
aqa
qa
]
,
[
qaa
qa
]
,
[
qa##
#
]
.
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 [
#
#q00100#
]
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#
] [
q00
2q7
] [
1
1
] [
0
0
] [
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): [
#
#21qa02#
]
.
We use the tiles [
aqa
qa
]
,
[
qaa
qa
]
to catch up and to finish the computation we use[
qa##
#
]
as follows [
#
#qa#
] [
qa##
#
]
.
The last detail is generalizing the modified version of the Post correspon-
dence problem to the original version. We suppose that ∗ and 3 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
b
]
in our original set of tiles we add
[ ∗t
b∗
]
and for the start tile[
t0
b0
]
we add
[
∗t0
∗b0∗
]
; we have to start with this tile otherwise no match is
possible. Finally, to end we add the tile
[∗3
3
]
.
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