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
Decidable problems are computational problems for which there exists an algorithm that can determine, in a finite amount of time, whether a given input has a specific property or satisfies a particular condition.
Undecidable problems are computational problems for which no algorithm can determine, in a finite amount of time, whether a given input has a specific property or satisfies a particular condition.
Decision Problems: Decision problems are computational problems that require determining whether an input meets certain criteria by providing either "yes" or "no" as an answer.
The halting problem is an undecidable problem that asks whether, given an arbitrary program and its input, it will eventually halt (terminate) or run forever.