The Post Correspondence Programming Language: Domino-oriented Programming (2015)

Summary

The Post Correspondence Programming Language: Domino-oriented Programming A Simple Puzzle Suppose you are given infinitely many of each of the following dominos: Can you find a way to arrange some of the dominos so that the sequence of dots on top row matches the bottom row? Here is one possible solution: This list of dominos is called a match since reading off the top row we get which is the same as reading off the bottom row. Determining whether a collection of dominos has a match is known as the Post Correspondence Problem, or PCP for short. Despite its simplicity, we can use PCP to compute mathematical functions by cleverly picking the dominos that are used. Computation via Dominos To demonstrate its potential for computation, we show how PCP can be used to calculate the least common multiple of two integers. Theorem: To compute the least common multiple of integers a and b, solve the Post Correspondence Problem for the dominos: The number of dots in the shortest match is LCM(a, b). The proof of this theorem is left as an exercise, but here is an example shortest match for a = 4 and b = 6: The number of dots in the top and bottom rows is LCM(4, 6) = 12. What else, besides LCM, can we compute using PCP? The answer is surprising: any computation that is doable on a Turing machine is doable using PCP. This implies that PCP, like Turing machines, can be used for general-purpose programming. To emphasize PCP as programming language, we will refer to it as the Post Correspondence Programming Language, or PCPL for short. This allows us to elegantly formalize PCP's computational power: Theorem: PCPL is Turing-complete. A proof of this theorem can be found in Michael Sipser's textbook Introduction to the Theory of Computation, second edition, section 5.2. This proof describes a series of steps to compile any Turing machine into an equivalent PCP instance (PCPL program). We've followed these steps to construct the PCPL program in the following example. PCPL Example Let M ...