If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

Undecidable problems

AP.CSP:
AAP‑4 (EU)
,
AAP‑4.B (LO)
,
AAP‑4.B.1 (EK)
,
AAP‑4.B.2 (EK)
,
AAP‑4.B.3 (EK)
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:
A diagram of the halt checking program. A box is shown with two inputs, program P and input I. Inside the box is a flow chart which starts with a diamond condition "Will program P halt with input Y?". An arrow labeled true leads to "RETURN "halts"" and an arrow labeled false leads to "RETURN "never"".
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:
A diagram of the reverser program. An outer box is shown with one input, program P. Inside the outer box, the input flows into the two inputs for the halt checker program, program P and input I. They flow into an inner box with a flow chart. It starts with a diamond condition "Will program P halt with input Y?". An arrow labeled true leads to "RETURN "halts"" and an arrow labeled false leads to "RETURN "never"". An arrow labeled "halts" flows out of the box from "RETURN "halts"" and into a "LOOP" node with an arrow that points back to itself. Another arrow labeled "never" flows out of the box from "RETURN "never"" and into an "END" node.
If we input the counting-down program into Reverser, it will see that HaltChecker returns "halts" and thus decide to loop infinitely.
A diagram of the reverser program. An outer box is shown with one input, CountDown. Inside the outer box, the input flows into the two inputs for the halt checker program. Those inputs flow into an inner box with a flow chart. It starts with a diamond condition "Will CountDown halt with input CountDown?". A highlighted arrow labeled true leads to "RETURN "halts"" and a faded arrow labeled false leads to "RETURN "never"". A highlighted arrow labeled "halts" flows out of the box from "RETURN "halts"" and into a "LOOP" node with an arrow that points back to itself. A faded arrow labeled "never" flows out of the box from "RETURN "never"" and into an "END" node.
If we input the counting-up program into Reverser, it will see that HaltChecker returns "never" and thus decide to return immediately.
A diagram of the reverser program. An outer box is shown with one input, CountUp. Inside the outer box, the input flows into the two inputs for the halt checker program. Those inputs flow into an inner box with a flow chart. It starts with a diamond condition "Will CountUp halt with input CountUp?". A faded arrow labeled true leads to "RETURN "halts"" and a highlighted arrow labeled false leads to "RETURN "never"". A faded arrow labeled "halts" flows out of the box from "RETURN "halts"" and into a "LOOP" node with an arrow that points back to itself. A highlighted arrow labeled "never" flows out of the box from "RETURN "never"" and into an "END" node.
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.
A diagram of the reverser program. An outer box is shown with one input, Reverser. Inside the outer box, the input flows into the two inputs for the halt checker program. Those inputs flow into an inner box with a flow chart. It starts with a diamond condition "Will Reverser halt with input Reverser?". A faded arrow labeled true leads to "RETURN "halts"" and a highlighted arrow labeled false leads to "RETURN "never"". A faded arrow labeled "halts" flows out of the box from "RETURN "halts"" and into a "LOOP" node with an arrow that points back to itself. A highlighted arrow labeled "never" flows out of the box from "RETURN "never"" and into an "END" node.
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.
A diagram of the reverser program. An outer box is shown with one input, Reverser. Inside the outer box, the input flows into the two inputs for the halt checker program. Those inputs flow into an inner box with a flow chart. It starts with a diamond condition "Will Reverser halt with input Reverser?". A highlighted arrow labeled true leads to "RETURN "halts"" and a faded arrow labeled false leads to "RETURN "never"". A highlighted arrow labeled "halts" flows out of the box from "RETURN "halts"" and into a "LOOP" node with an arrow that points back to itself. A faded arrow labeled "never" flows out of the box from "RETURN "never"" and into an "END" node.
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?

  • male robot johnny style avatar for user Kyle Stauffer
    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?
    (13 votes)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user Abhishek Shah
      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!
      (10 votes)
  • blobby green style avatar for user vivianhui05
    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)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user Abhishek Shah
      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!
      (7 votes)
  • female robot amelia style avatar for user Ethan Braden
    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)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user Abhishek Shah
      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)
  • blobby green style avatar for user samer.zo3mot
    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)
    Default Khan Academy avatar avatar for user
    • leaf green style avatar for user Shane McGookey
      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)
  • leaf red style avatar for user layaz7717
    How do you exit an infinite loop if it happens on your browser?
    (1 vote)
    Default Khan Academy avatar avatar for user
  • leaf red style avatar for user layaz7717
    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)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user NAVEED RIAZ
    So in the absence of a halt predicting algorithm, do v have software or algorithm to indirectly predict the same by keeping a track of time taken by the algorithm? When the time is up the monitoring algorithm will stop the one which was being executed.
    (0 votes)
    Default Khan Academy avatar avatar for user
    • aqualine ultimate style avatar for user Martin
      You can do that, if you have a rough idea how long your algorithm is supposed to take.
      For example you could code a loop to break if it has run a million times.

      But there isn't an algorithm that allows you to wholly circumvent the problem. A compiler for instance won't be able to tell you if you're about to send it into an infinite loop.
      (1 vote)
  • eggleston blue style avatar for user DanielC
    cacaaaacacacacacacacacaccacacacaaccacacacccacacacacaacacacaacacacacacaccaccaacacacacacacacacacacacaccacacacccccacacacacaccaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaacaccacaacccacacacacacacacacaaccacacacacacacacacaacacacacacacacacacacacaacacacacacacacacacacacacacacacacacacacacacacacacaccacaacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacaccacacacacacacacacacacacacacacaccaaccacacaaccacacacaacaccacacacacacacacacaaccaaccacacaadidkdikdikdikdikdidkdikdidkidkidkdiididdiidkididkidikdkidkikiiiiiiiiiiiiiiiiidikdkidikdikdikdkidikdikdikdikdidddkkikdikdikdikdikdikidikdididikdkidikdidikdikdikdidikdikdidididididiidikdikddidiidikdkidikdidkidkdikikdidikdikdidkdkidkidikdididikidkidkidikdiikdiiiiiiiiiiiiiiiiiiiiiiiiiiii
    (0 votes)
    Default Khan Academy avatar avatar for user
  • aqualine ultimate style avatar for user amoon0153
    Why do undecidable problems matter in computer science?
    (0 votes)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user Abhishek Shah
      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
      (3 votes)