Some problems aren’t slow or hard. They’re impossible — no algorithm can exist, on any computer, ever. Meet the most famous one, and learn to never confuse “impossible” with “takes forever.”
No reading — this page is the reading. Runestone doesn’t cover Unit 4 (search, efficiency, limits, simulation), so everything you need is right here.
Programs, Algorithms region — the far edge of it. 4.7 found problems that are slow. Today’s problems aren’t slow. No algorithm for them can exist at all, on any computer, ever.
Card 1: “The sentence on Card 2 is true.”
Card 2: “The sentence on Card 1 is false.”
Is Card 1 true? Then Card 2 is true, so Card 1 is false. Is Card 1 false? Then Card 2 is false, so Card 1 is true. There is no answer that works. Sit with that for a second — because a computer program can be built to do exactly the same thing.
A decision problem has a yes-or-no answer: “Is this number even?” “Is this name in the list?” A problem is decidable if an algorithm can be written that gives the correct yes-or-no answer for every input.
An undecidable problem is one for which no algorithm can be constructed that always gives a correct yes-or-no answer. Not a slow one. Not a hard one. None.
“Given any program and its input, will the program eventually stop, or run forever?” For
lots of individual programs you can tell. But suppose someone claims they wrote
halts(program, input) that answers correctly for every program. Build this:
def contrarian(program): if halts(program, program): while True: # loop forever pass else: return # stop at once
PROCEDURE contrarian(program) { IF (halts(program, program)) { REPEAT UNTIL (false) { } } ELSE { RETURN } }
contrarian asks halts what a program will do, then does the
opposite. Now feed contrarian to itself. Whatever halts predicts, contrarian does
the other thing — Card 1 and Card 2 again. So a perfect halts can’t exist. That’s
all you need: the exam asks you to recognize undecidable problems, not prove anything.
| Unreasonable time (4.7) | Undecidable (today) | |
|---|---|---|
| Is there an algorithm? | Yes | No — can’t exist |
| The problem | It would take too long | No algorithm always answers correctly |
| Faster computer helps? | A little — never enough | Not at all |
| Example | Best route through 50 cities | The halting problem |
If an answer choice says “undecidable because it would take too long,” it’s wrong.
Part 1. For these three small programs, you can decide. Will each one stop?
Part 2. Now you’re halts, and someone runs
contrarian(contrarian). What do you predict?
Five questions. At least one is baited with “it would take too long.”
Could someone write a program that looks at any other program and correctly says whether it will ever do something malicious? It runs into the same wall as the halting problem: in general, deciding what an arbitrary program will eventually do is undecidable.
So real antivirus software uses — you guessed it — heuristics: suspicious patterns, known signatures, odd behavior. It catches most threats and misses some, forever. That’s not a failure of effort. It’s a limit of computing itself.