Post correspondence problem
Problema de correspondencia de Post
- Date
- 1946 · confidence high
- Place
- New York City, New York, United States
- Credited to
- Emil Leon Post
- Field
- Knowledge & symbols
What was discovered
Emil Post formulated a decision problem about lists of word-labeled dominoes that turned out to be undecidable, simpler to state than the halting problem.
What it led to
- Undecidability proofs in logic
- Proof that certain grammars are ambiguous
- Teaching of computability theory
- Applications in formal language theory