3.18 Undecidable Problems

What you need to know

• A decidable problem is one for which an algorithm exists that gives a correct yes/no answer for every possible input. "Is this number even?" is decidable.
• An undecidable problem is one for which no such algorithm can exist. It's not that we haven't found one — it has been proven that none can exist.
• Undecidable ≠ unreasonable time. An unreasonable-time problem has an algorithm, just a slow one. An undecidable problem has no algorithm that works for all inputs.
• The classic example is the halting problem: no general algorithm can determine, for every possible program and input, whether that program will eventually stop or run forever.
• An algorithm may solve some instances of an undecidable problem (you can tell that DISPLAY("hi") halts), but no single algorithm solves all instances.
• This is a theoretical limit of computing — a boundary that faster hardware or cleverer programming cannot move.

Worked example

Someone claims to have written willHalt(program, input) that returns true if the program stops and false if it loops forever. Sure, it works on simple cases. But it can be shown that any such procedure must fail on at least one input — a program constructed to do the opposite of whatever willHalt predicts about it. That contradiction is why the halting problem is undecidable. The takeaway for the exam is just the conclusion: no general solution exists.

Going deeper

The nuance, edge cases, and connections that turn a 3 into a 5.

• A decidable problem is one where an algorithm can be written that gives a correct yes/no answer for every possible input. An undecidable problem is one where no such algorithm can exist — this has been mathematically proven, not just not-yet-found.
• The halting problem: given any program and any input, will the program eventually stop? Alan Turing proved in 1936 that no algorithm can answer this for all programs. The proof constructs a program that does the opposite of whatever the supposed halting-detector predicts about it, creating a contradiction.
• Undecidability is not about difficulty or time. An unreasonable-time problem has an algorithm that's too slow. An undecidable problem has no algorithm at all, regardless of time. They're separate categories on the exam.
• An undecidable problem can still be solved for specific instances. You can tell that DISPLAY("hi") halts and REPEAT UNTIL (false) doesn't. What's impossible is one algorithm that works for every program.
• Real consequences: no tool can perfectly detect all infinite loops, all bugs, or all malware — because each of those reduces to the halting problem. Tools use heuristics and catch most cases; the impossible part is catching all.
• This is one of the few places the CED touches theoretical computer science. The exam expects you to know: some problems are provably unsolvable by computers, the halting problem is the example, and this is a fundamental limit rather than a current-technology limit.

Mistakes that cost points

• Saying an undecidable problem "hasn't been solved yet." It's been proven unsolvable. "Yet" is wrong.
• Suggesting a faster computer or heuristic. Those address unreasonable time, not undecidability. No algorithm exists to speed up.
• Thinking undecidable means no instance can be solved. Specific cases often can. The claim is about a general algorithm for all cases.

Practice questions

Written in the style of the real exam. Try each one before revealing the answer.