CSci 301 Lecture Notes

Week Eight, Tuesday: A Simple Undecidable Problem

Post's correspondence problem (PCP) is a good example of an easily desribed problem that is not computationally solvable. In addition, the PCP is useful in proving that other problems are undecidable.

The key to understanding why the PCP is undecidable (aside from the proof of undecidability by reduction from the acceptance problem) is to note that the driver of complexity in the PCP is the maximum string length in the domino set. For a given maximum string length n, an algorithm can be produced for deciding if a match exists. However, the algorithm found for a particular n will not decide a PCP for n + 1. A new algorithm must be found for each n-version of the problem.

Contrast this situation with some of the common algorithms with which we are familiar, like an algorithm for sorting. We can apply the same algorithm to any list of n elements and get our desired result.

Email: Richard dot J dot Wagner at gmail dot com