The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability.
Read more about Post Correspondence Problem: Definition of The Problem, Proof Sketch of Undecidability, Variants
Famous quotes containing the words post and/or problem:
“Fear death?—to feel the fog in my throat,
The mist in my face,
When the snows begin, and the blasts denote
I am nearing the place,
The power of the night, the press of the storm,
The post of the foe;
Where he stands, the Arch Fear in a visible form,
Yet the strong man must go:”
—Robert Browning (1812–1889)
“The general public is easy. You don’t have to answer to anyone; and as long as you follow the rules of your profession, you needn’t worry about the consequences. But the problem with the powerful and rich is that when they are sick, they really want their doctors to cure them.”
—Molière [Jean Baptiste Poquelin] (1622–1673)