Undecidable problems are decision problems for which it is impossible to construct an algorithm that always leads to a correct answer. The halting problem is an example of an undecidable problem, as there is no algorithm that can correctly determine whether arbitrary programs will eventually halt when run. These concepts are studied in computability theory and computational complexity theory.
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