Post's correspondence problem (idea)

Definition: Given an alphabet S, one instance of Post's correspondence problem of size s is a finite set of pairs of strings (g_i , h_i) ( i = 1...s s>=1) over the alphabet S. A solution of length n >= 1 to this instance is a sequence i₁ i₂ ... i_n of selections such that the strings g_i1g_i2 ... g_in and h_i1h_i2 ... h_in formed by concatenation are identical.*

Basically, you've got two sets of strings composed from the same alphabet. You have to build a new string that is some arrangement of strings taken from the first set. This string must also match a string that can be built from the strings available in the second set. The only other qualification is that the list of index numbers for the strings used from the first set must be the same as the list of index numbers of the strings used from the second set. The new string you're forming can be arbitrarily long.

It's been shown that this problem is recursive but not recursively enumerable (recursive in the sense of being decidable, not solvable by recursion in programming). That means that you can recognize instances of the PCP that are solvable, but you can't build a program that will look at an arbitrary instance of PCP and decide whether there's a solution. This puts it in the same class of problems as the halting problem. If you could solve arbitrary instances of PCP, you could solve arbitrary instances of the halting problem (which you certainly can't).

Also note that the acronym is PCP, also the acronym used for the dissociative anaesthetic (and drug of abuse) phencyclidine. Imagine the world of puns you can create from this:

"How's the problem set coming?"
"I just wish I didn't have to do all this goddamn PCP."

Yeah, sorry, that was pretty lame. Couldn't resist.

*Text of definition shamelessly copied from http://www.cs.ualberta.ca/~zhao/PCP/intro.htm