[1] Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability.
The input of the problem consists of two finite lists
, such that The decision problem then is to decide whether such a solution exists or not.
This gives rise to an equivalent alternative definition often found in the literature, according to which any two homomorphisms
with a common domain and a common codomain form an instance of the Post correspondence problem, which now asks whether there exists a nonempty word
in the domain such that Another definition describes this problem easily as a type of puzzle.
We begin with a collection of dominos, each containing two strings, one on each side.
The Post correspondence problem is to determine whether a collection of dominos has a match.
A convenient way to view an instance of a Post correspondence problem is as a collection of blocks of the form
Thus the above example is viewed as i = 1 i = 2 i = 3 where the solver has an endless supply of each of these three block types.
A solution corresponds to some way of laying blocks next to each other so that the string in the top cells corresponds to the string in the bottom cells.
., 2, 3) is a solution (in addition to all their repetitions): 1 2 2 2 3 The most common proof for the undecidability of PCP describes an instance of PCP that can simulate the computation of an arbitrary Turing machine on a particular input.
A match will occur if and only if the input would be accepted by the Turing machine.
The following discussion is based on Michael Sipser's textbook Introduction to the Theory of Computation.
According to the definition of a Turing machine, the full state of the machine consists of three parts: Although the tape has infinitely many cells, only some finite prefix of these will be non-blank.
Next, for each symbol a in the tape alphabet, as well as #, we have a "copy" block, which copies it unmodified from one state to the next: We also have a block for each position transition the machine can make, showing how the tape head moves, how the finite state changes, and what happens to the surrounding symbols.
To allow this, we extend the computation so that once an accepting state is reached, each subsequent machine step will cause a symbol near the tape head to vanish, one at a time, until none remain.
If qf is an accepting state, we can represent this with the following transition blocks, where a is a tape alphabet symbol:
There are a number of details to work out, such as dealing with boundaries between states, making sure that our initial tile goes first in the match, and so on, but this shows the general idea of how a static tile puzzle can simulate a Turing machine computation.
is represented as the following solution to the Post correspondence problem: ...