Concept

Post correspondence problem

Overview

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.

Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).

Related ideas

• Finite set
• If and only if
• Turing machine
• Emil Leon Post
• Decision problem
• Entscheidungsproblem
• Halting problem

Place in the tradition

Part of Outline of logic.

Explore Post correspondence problem in the interactive graph →