The Post Correspondence Programming Language: Domino-oriented Programming David Lazar
A Simple Puzzle
Suppose you are given infinitely many of each of the following dominos:
1 2 3
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:
3 2 3 1
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
... continue reading