Undecidable Problems
This page will teach you about Undecidable Problems in programming.
What is an Undecidable Problem?
An undecidable problem is a problem where no algorithm can always give a correct yes or no answer for every possible input.
This does not mean computers are slow or not powerful enough — it means it is mathematically impossible to write such a program, no matter how good the programmer is.
Even if a problem is very difficult, it can still be decidable.
Undecidable means impossible, not just hard.
The Halting Problem
The most famous undecidable problem is the halting problem:
Can you write a program that looks at any other program and its input, and correctly determines whether that program will eventually stop (halt) or run forever?
The answer is no. It has been proven that no such program can exist.
For example, a program with a loop might run forever—or it might stop depending on conditions. There is no general algorithm that can correctly decide this for all programs.
Think of it this way — if you tried to build that program, you could always construct a case that breaks it, causing a contradiction.
Decidable vs Undecidable
| Type | Definition | Example |
|---|---|---|
| Decidable | An algorithm always gives a correct yes/no answer for every input | Is this number even? |
| Undecidable | No algorithm can always give a correct yes/no answer for every input | Will this program halt or run forever? |
Why This Matters
- It shows that some problems cannot be solved by algorithms
- It helps us understand the limits of computing
- It explains why we can’t automate every possible task
AP Style Question
Which of the following best describes an undecidable problem?
- A. A problem that takes too long for a computer to solve
- B. A problem that can only be solved with a very powerful computer
- C. A problem for which no algorithm can always produce a correct yes or no answer for every possible input
- D. A problem that has not yet been solved but may be solved in the future