Topic 3.18 Notes – Undecidable Problems

What a Decidable Problem Is

Everything here revolves around a decision problem, which is a problem that has a yes-or-no answer.

Examples:

• “Is this number divisible by 3?”
• “Is this password at least 8 characters long?”
• “Is this list sorted in increasing order?”

A problem is decidable if:

• An algorithm exists
• It produces the correct yes/no answer
• For every possible input

That “every possible input” part is the dealbreaker.

If even one input makes the algorithm:

• Crash
• Loop forever
• Give a wrong answer

then the problem is not decidable.

A quick example:

“Is a number even?”

You can write an algorithm that checks number MOD 2 = 0.
That works for all integers. So this problem is decidable.

Important:
Decidable does not mean fast.
A problem can take an extremely long time and still be decidable. That connects to the efficiency topic you studied earlier. Efficiency is about time. Decidability is about possibility.

If an algorithm is guaranteed to work for every case, even if it’s slow, the problem is decidable.

What an Undecidable Problem Is

An undecidable problem is still a decision problem. It still asks yes or no.

The difference is this:

There is no possible algorithm that can:

• Always give the correct answer
• For all possible inputs

This is not about humans not being smart enough yet. It means no such algorithm can ever exist.

You are not expected to prove that something is undecidable. That kind of proof is beyond AP CSP. What you need to understand is that these problems exist.

When you see wording like:

• “There is no algorithm that works in all cases.”
• “No general solution exists.”
• “It is impossible to determine for every input.”

that signals undecidable.

Some Instances Can Be Solved

This is where people get tripped up.

An undecidable problem can still have some inputs that are solvable.

What makes it undecidable is that:

• There is no single algorithm that works for every input.

Think of it like this:

If even one possible input cannot be handled correctly by the algorithm, the problem is not decidable.

On multiple-choice questions, watch for traps like:

“The algorithm correctly solves most cases but cannot determine the answer for certain inputs.”

That means it is undecidable, because the guarantee is broken.

The AP exam cares about that guarantee more than anything else.

The Halting Problem

The most famous undecidable problem is the Halting Problem, introduced by Alan Turing in 1936.

The question is simple:

Given a program and an input, will the program eventually stop running?

In other words:

• Will it halt?
• Or will it run forever?

One way to imagine this is with a hypothetical “halt checker” that tries to analyze any program and input:

The diagram shows a HaltChecker that takes a program P and an input I, then outputs either “halts” or “never.” The larger “Reverser” construction uses that answer to create a contradiction, which is the heart of Turing’s proof.

Turing proved that:

• There is no algorithm that can correctly answer this question
• For every possible program and input

Why this matters:

Programs can:

• Contain loops
• Call other programs
• Even simulate other programs

Trying to predict all possible program behavior leads to logical contradictions. So a universal “halt checker” is impossible.

This is the classic example you’ll see referenced on tests.

Why Undecidable Problems Matter

This connects directly to the big idea of limits of computation.

There are two different kinds of limits:

1. Efficiency limits

Some problems are solvable, but take unreasonable time (like exponential growth).
These are still decidable.

2. Fundamental limits

Some problems cannot be solved at all by any algorithm.
These are undecidable.

Here’s the clean comparison:

When the AP exam tests this, they usually describe a scenario and ask whether an algorithm can exist that solves it for every case. Your job is to focus on the guarantee.

If the answer cannot be guaranteed for all inputs, the problem is undecidable.