Post's correspondence problem is an undecidable problem useful in categorizing other problems as undecidable.
