What is the halting problem?

The halting problem is a decision problem that specifies the undecidability of an output of a computer program. It asks the following question: given a program and an input, will the program halt, or will it execute forever?

We can neither predict the answer to this question, nor form any algorithm to help us determine its answer.

In computational theory, these programs run on Turing machines. A Turing machine is an automaton that represents recursively enumerable languages.

Halting and non-halting programs

A program with a simple print statement like print("Hello World") is a halting program. Meanwhile, an infinite loop like while(true){} is an example of a non-halting program.

Example

#include <iostream>
using namespace std;
int main() {
  // A halting code
  cout << "Hello World"<<endl;
  // An infinite loop
  while(true){
    cout<<""<<endl;
  }
  return 0;
}

Note: We can draw the conclusions above by simply looking at the program. However, such predictions are not easy to make in the case of complex Turing machines.

Proof by contradiction

Given a Turing machine and an input, we can determine whether the machine completes the task in a finite amount of time.

Let's assume the existence of a Turing machine that can determine the decidability of a computation. The input we give to the Turing machine outputs "Halts" when the computation completes in a finite amount of time. It outputs "Does not halt" when the machine goes into an infinite loop. Let's call this machine M1.

Our Turing machine tells us if a program halts or not

Also, let's suppose another machine takes a program as an input and passes it through H1. If the output of H1 is "Halts," the machine goes into an infinite loop. On the contrary, if the output of H2 is "Does not halt," the machine halts. Let's name this machine M2.

Our second Turing machine uses M1 in its computation

Now, if we run M2 on M2, we see that if H1 returns "Halts," the final output is "Does not halt." If H1 returns "Does not halt," the final output is "Halt." In this case, we see a contradiction—H1 says that a particular program halts, but actually does not halt.

Therefore, we conclude that H1 is wrong. Hence, our assumption about the existence of such a Turning machine is proven false.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved