The Post correspondence problem is an undecidable decision problem introduced by Emil Post in 1946. It is simpler than the halting problem and the Entscheidungsproblem, and is often used to prove undecidability. It involves finding a sequence of moves that satisfies certain conditions.
Carnegie Mellon University
Spring 2015
A foundational course that introduces formal languages, automata, computability, and complexity theories, including finite automata, Turing machines, and P/NP classes.
No concepts data
+ 35 more concepts