Written by the Fiveable Content Team • Last updated September 2025
Verified for the 2026 exam
Verified for the 2026 exam•Written by the Fiveable Content Team • Last updated September 2025
Definition
An undecidable problem is a computational problem for which no algorithm can determine whether a given input has a specific property or satisfies a certain condition.
A decidable problem is the opposite of an undecidable problem; it refers to computational problems for which there exists an algorithm that can determine whether a given input has a specific property or satisfies a certain condition.
The halting problem refers to the question of whether an arbitrary program will halt (terminate) or run forever when executed on some input.
Gödel's Incompleteness Theorems: These theorems, proved by Kurt Gödel, state that in any formal system of mathematics, there will always be true statements that cannot be proven within the system itself.