3.18 Undecidable Problems

TLDR

A decidable problem is a yes or no question where an algorithm always gives the correct answer for every possible input. An undecidable problem is one where no single algorithm can always give a correct yes or no answer, even though some specific cases might still be solvable. In AP Computer Science Principles, you need to explain that undecidable problems exist and recognize the difference between problems computers can always solve and problems they cannot.

more resources to help you study

practice multiple choiceFRQ practice & scoringcheatsheetsscore calculator

Why This Matters for the AP Computer Science Principles Exam

This topic shows up on the multiple-choice section, where you may be asked to identify a problem as decidable or undecidable or to explain why some problems have no complete algorithmic solution. It pairs naturally with algorithmic efficiency: that topic covers problems that take too long to solve, while this topic covers problems that cannot be solved by any algorithm for all inputs. You will not be asked to prove that a specific problem is undecidable, since that is outside the scope of the course and exam. The goal is to explain that undecidable problems exist and describe what makes them different from decidable ones.

Key Takeaways

• A decision problem is any problem with a yes or no answer, like "Is this number even?"
• A decidable problem has an algorithm that produces a correct answer for all possible inputs.
• An undecidable problem has no algorithm that can always give a correct yes or no answer for every input.
• Undecidable does not mean unsolvable in every case. Some individual instances of an undecidable problem can still be solved.
• The exam asks you to explain that undecidable problems exist, not to prove a problem is undecidable.

Decidable vs Undecidable Problems

Start with the idea of a decision problem: a question that has only two possible answers, yes or no. "Is this number even?" is a decision problem because every number is either even or not.

A decidable problem is a decision problem where you can write an algorithm that gives the correct yes or no answer for every possible input. The "is this number even?" example is decidable because you can check it with a simple rule for any number you are given.

An undecidable problem is a decision problem where no algorithm can be written that always gives a correct yes or no answer. The key word is "always." For an undecidable problem, you cannot build one algorithm that handles every possible input correctly.

Here is the part students often miss: an undecidable problem can still have some instances that are solvable. You might be able to answer the question correctly for certain specific inputs. What makes the problem undecidable is that there is no single algorithm that works for all inputs.

The Halting Problem (Example)

The most famous undecidable problem is the halting problem, which Alan Turing described in 1936. The halting problem asks whether you can write one algorithm that takes any program as input and correctly answers the question, "Will this program eventually stop running, or will it run forever?"

Turing showed that no such algorithm can exist that works for every possible program. This is the classic illustration that some problems simply cannot be solved by an algorithm for all inputs.

Treat the halting problem as a helpful example, not as required content you must memorize in detail. The exam wants you to understand the concept of undecidability, and you will not need to reproduce a formal proof.

How to Use This on the AP Computer Science Principles Exam

MCQ

• Read the problem carefully and decide if it is a decision problem (yes or no answer) first.
• If an algorithm can correctly answer for every input, it is decidable. If no algorithm can always answer correctly, it is undecidable.
• Watch for answer choices that confuse "undecidable" with "takes too long." Those are different ideas. A slow problem can still be decidable.

Common Trap

• Do not assume undecidable means "impossible to ever answer." Some specific cases of an undecidable problem can still be solved. The issue is that no one algorithm covers all inputs.

Common Misconceptions

• "Undecidable means a computer can never give an answer." Not quite. A computer can answer some individual cases. The problem is that no single algorithm works for every input.
• "Undecidable is the same as inefficient or slow." These are separate ideas. An inefficient problem might still be decidable, it just takes a long time. An undecidable problem has no algorithm that always works, no matter how much time you allow.
• "Every problem has an algorithmic solution if you write good enough code." Some problems are undecidable, so no amount of clever coding produces an algorithm that handles all inputs correctly.
• "You need to prove a problem is undecidable on the exam." You only need to explain that undecidable problems exist and what makes them different from decidable ones.

Related AP Computer Science Principles Guides

• 3.1 Variables and Assignments
• Big Idea 3: Algorithms and Programming
• 3.12 Calling Procedures
• 3.17 Algorithmic Efficiency
• 3.2 Data Abstraction
• 3.10 Lists