Main content

## AP®︎/College Computer Science Principles

### Unit 4: Lesson 3

Solving hard problems# 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`

: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?(13 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!(10 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!(7 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)

- 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)

- 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)

- 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)
- 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)

- cacaaaacacacacacacacacaccacacacaaccacacacccacacacacaacacacaacacacacacaccaccaacacacacacacacacacacacaccacacacccccacacacacaccaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaacaccacaacccacacacacacacacacaaccacacacacacacacacaacacacacacacacacacacacaacacacacacacacacacacacacacacacacacacacacacacacacaccacaacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacaccacacacacacacacacacacacacacacaccaaccacacaaccacacacaacaccacacacacacacacacaaccaaccacacaadidkdikdikdikdikdidkdikdidkidkidkdiididdiidkididkidikdkidkikiiiiiiiiiiiiiiiiidikdkidikdikdikdkidikdikdikdikdidddkkikdikdikdikdikdikidikdididikdkidikdidikdikdikdidikdikdidididididiidikdikddidiidikdkidikdidkidkdikikdidikdikdidkdkidkidikdididikidkidkidikdiikdiiiiiiiiiiiiiiiiiiiiiiiiiiii(0 votes)
- Why do undecidable problems matter in computer science?(0 votes)
- 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)