Main content
AP®︎/College Computer Science Principles
Course: AP®︎/College Computer Science Principles > Unit 4
Lesson 3: Solving hard problemsUndecidable problems
Some problems take a very long time to solve, so we use algorithms that give approximate solutions. There are some problems that a computer can never solve, even the world's most powerful computer with infinite time: the undecidable problems.
An undecidable problem is one that should give a "yes" or "no" answer, but yet no algorithm exists that can answer correctly on all inputs.
The halting problem
Alan Turing proved the existence of undecidable problems in 1936 by finding an example, the now famous "halting problem":
Based on its code and an input, will a particular program ever finish running?
For example, consider this program that counts down:
num ← 10
REPEAT UNTIL (num = 0) {
DISPLAY(num)
num ← num - 1
}That program will halt, since
num eventually becomes 0. Compare that to this program that counts up:
num ← 1
REPEAT UNTIL (num = 0) {
DISPLAY(num)
num ← num + 1
}It counts up forever, since
num will never equal 0.Algorithms do exist that can correctly predict that the first program halts and the second program never does. These are simple programs which don't change based on different inputs.
However, no algorithm exists that can analyze any program's code and determine whether it halts or not.
In order to prove that such an algorithm cannot possibly exist, Turing used a "proof of contradiction".
We start by imagining that an algorithm does exist that can determine a program's haltability.
Then we propose a program called
HaltChecker that takes two inputs, a program's code and an input for that program. It then uses that hypothetical haltability algorithm to return either "halts" or "never".This flow chart visualizes
HaltChecker:If we input those earlier programs into
HaltChecker, we'd see the counting-down program results in "halts" and the counting-up program results in "never". Note that it's not actually running the programs, it's looking at their code and deciding based on the code structure.But now we propose a program called
Reverser. It takes a single input, a program's code. It sends HaltChecker that program as both the program to analyze and the input for the program. HaltChecker then determines if the input program halts when given itself as input. If HaltChecker returns "halts", Reverser runs an infinite loop. If HaltChecker returns "never", Reverser immediately returns.This flow chart visualizes
Reverser:If we input the counting-down program into
Reverser, it will see that HaltChecker returns "halts" and thus decide to loop infinitely.If we input the counting-up program into
Reverser, it will see that HaltChecker returns "never" and thus decide to return immediately.Reverser is a strange program indeed. It halts when it finds out that another program doesn't halt and likes to go on forever when it finds out another program does halt. That's weird but that's okay, strange programs are allowed in the world.But here's where it all falls apart: what happens if we input
Reverser itself into Reverser? HaltChecker analyzes the Reverser code to determine whether it halts. If it decides that it doesn't halt, then it returns "never". Reverser sees that result and returns immediately.But, wait a second!
HaltChecker just claimed that Reverser never halts, and then it went ahead and halted. HaltChecker did not give us a correct answer.What if
HaltChecker returns "halts" instead? When Reverser sees that result, it loops infinitely. HaltChecker just claimed that Reverser halts, and yet, it went on forever. Once again, HaltChecker did not give us a correct answer. In fact, there's no way for HaltChecker to give us a correct answer in this situation. Thus, we've proved that a perfectly correct halt-predicting algorithm can never exist and that the halting problem is undecidable.
It took me a while to really understand the halting problem. If you're having some trouble too, this animated video might be helpful.
More undecidable problems
Computer scientists and mathematicians have discovered many more undecidable problems. Quite a few of those, once simplified, look like another case of the halting problem. Generally, all the undecidable problems revolve around the difficulty of determining properties about the input and output of programs.
It's helpful to realize when we're dealing with an undecidable problem. We can then accept that our program can't correctly answer yes or no on all inputs, and come up with a different approach.
For example, our Khan Academy programming environment tries to avoid running programs with infinite loops, to prevent the poor browser from freezing. But how can we know that a program has an infinite loop? We can't, that's undecidable! Instead, we monitor how long loops take, and when a loop takes too long, we refuse to run the code. We can't know for sure if that loop was going to go on forever, but for our purposes, it's better to be safe than sorry.
🙋🏽🙋🏻♀️🙋🏿♂️Do you have any questions about this topic? We'd love to answer—just ask in the questions area below!
Want to join the conversation?
Are there any real-life examples of the halting problem, or is it just more or less to explain that the "perfectly correct halt-predicting algorithm" concept is not feasible?(15 votes)
Wonderful question.
Now that we know the halting problem is undecidable, what can we conclude from this? Suppose we want to detect if a program is a virus or not. This is a real-world task companies would like to solve.
However, using a technique known as a reduction, building another program (X) to automatically detect if a program (Y) is a virus or not is undecidable. Intuitively, when X is given a Y, everything is fine, but when X is given X, then contradictions occur.
Hence, this task is not solvable for all possible programs. However, for some real-world programs, you can detect if it's a virus or not, which is why Anti-virus tools exist.
I hope this helps!(13 votes)
- If it's impossible for the "halt checker" to exist once a reverser is put on it wouldn't that make it impossible for anything to exist accurately every time? For example, if a computer were supposed to calculate whether the temperature was below freezing or not, but then a reverser is put into it, then every output of the computer will be wrong. Is it true that with a reverser nothing can exist accurately (not just a "halt checker")? Sorry that my question is confusing but I didn't know how to word it.(4 votes)
- I think there might be a misunderstanding. Halt checker and reversers can both exist. However, they may not be fully accurate (i.e. they might be wrong in their checking). The impossibility result applies to the bold term in this claim: "perfectly correct halt-predicting algorithm can never exist"
I hope this helps!(8 votes)
I don't understand why the halting problem is a problem. Instead of looking for a program that 100% of the time correctly says if an algorithm ever ends why don't we make a program that runs the algorithm X amount of times where X is the point where it would take too long or not be cost-effective to continue running the algorithm and if it reaches the X value without stopping it returns that the algorithm never ends and if it stops before X then it returns that the algorithm does end. Just before we were talking about how sometimes we can allow a program to be incorrect some of the time if most of the time it is correct and I feel like this is one of those situations(4 votes)- This is a great insight: sometimes we don't need 100% accuracy. Approximate answers are sufficient even if we can't solve the halting problem with 100% accuracy. Your idea forms the basis of a field called program analysis that seeks approximate answers to questions about programs such as is a program a virus?(2 votes)
Why do undecidable problems matter in computer science?(1 vote)- Great question! They form the basis for a class of problems that computers cannot perfectly solve. Hence, scientists do not have to spend time trying to find a perfect solution since the problem can't be solved perfectly and can better spend their time finding approximate solutions(6 votes)
- How can you give CountDown (the program) as the input to the program CountDown? Isn't that invalid input to Countdown? What does CountDown accept as valid input?(3 votes)
You can certainly pass one program as input into another program. Recall that a "program" is simply binary machine code, represented as 1s and 0s. Thus, it does not differ significantly from passing in a number or a character, which will also inevitably be simple 1s and 0s.
In the case of the CountDown program, I am not certain what its valid inputs are given that they are not specified, but there is nothing restricting it from taking program code as an input. However, this would not influence its behavior, as its count down does not rely on the program's input. It will halt irregardless when the count reaches 0.(2 votes)
num ← 1
REPEAT UNTIL (num = 0) {
DISPLAY(num)
num ← num + 1
}
can anyone give me this code in Python I can not understand how to change it.(1 vote)
num = 1
while num != 0:
print(num)
num = num + 1(2 votes)
How do you exit an infinite loop if it happens on your browser?(1 vote)- Hello. I was on a website, and when I clicked a certain button, it reloaded again and again without stopping, and I had to exit the tab. This has happened multiple times. Would this be an example of an infinite loop?(1 vote)
- Perhaps. You really can't tell in finite time if a loop is infinite. Perhaps in 100 years, it would have terminated. Maybe even 1000 years? For all practical purposes, yes it likely was an "infinite loop"(1 vote)
Is what you're using pseudocode or an older language?(1 vote)
The code that is in this article is AP CSP exam pseudocode — https://www.khanacademy.org/computing/ap-computer-science-principles/ap-csp-exam-preparation/learn-ap-csp-exam-pseudocode/a/ap-csp-exam-pseudocode-reference(1 vote)
"If we input the counting-down program into Reverser, it will see that HaltChecker returns "halts" and thus decide to loop infinitely."
Reverser will try and input 'counting-down' into 'counting-down' but 'counting-down' is not a valid input for it. Shouldn't it error instead of giving a result. Or does 'halt' mean it will error?
---
Similar with the 'reverser' paradox. The reverser that is used as an input will itself need an input before it could be run. If a valid input is given, then wouldn't it be able to work it out?
Since this is a whole field of study, I'll assume I'm wrong about something but I'm not sure what.(1 vote)- Counting-up and Counting-down are not good examples for the HaltChecker because they don't require inputs. Just assume that giving them inputs doesn't change anything.
The reverser that is used as an input is not a function, it's the code for the function.
For example, the reverser code is:PROCEDURE reverser (program) {
willStop ← HaltChecker (program, program)
IF (willStop = "halts") {
//Loop
REPEAT UNTIL (1 = 2) {
}
}
}
then you will run reverser("willStop ← HaltChecker, etc...").
And for Count-up you run reverser("num ← 10, etc...")
I hope you understand. If not, I strongly recommend watching the video linked on the page (https://www.youtube.com/watch?v=92WHN-pAFCs).(1 vote)
