3.18 Undecidable Problems

What is an undecidable problem?

An undecidable problem is a problem for which no algorithm can be built that always produces a correct yes/no answer for all possible inputs. This isn't about needing more time or computing power — it's proven that no algorithm can ever exist, no matter how much computing power we have.

Decidable vs. undecidable

A decidable problem can be solved by an algorithm in a finite amount of time, guaranteed to halt with a correct answer. Undecidable problems, however, have no such algorithm — some inputs may cause any proposed solution to loop forever or fail to give a correct result.

The Halting Problem

The classic example is the Halting Problem: determining whether an arbitrary program will finish running (halt) or run forever, given its input. It's been mathematically proven no general algorithm can solve this for all possible programs and inputs, making it a foundational example of undecidability.

Key terms

Undecidable problem

A problem for which no algorithm can be constructed that always leads to a correct yes/no answer for all inputs.

Decidable problem

A problem that can be solved by an algorithm that always halts with a correct answer in finite time.

Halting Problem

The classic undecidable problem: determining whether an arbitrary program will finish running or run forever, given its input.

Why is undecidability a limit, not a technology issue?

It's mathematically proven that no algorithm—regardless of speed or resources—can ever solve an undecidable problem for all cases.

Key implication of undecidability

Some problems can never be fully automated by any computer program, no matter how advanced technology becomes.

Try an AP-style question

What is an undecidable problem?

1. One that takes only a few seconds
2. One whose answer is always yes
3. One no algorithm solves for all inputs
4. One solved quickly by binary search