The Halting problem

We learn about the halting problem in computability theory. It is as follows, Given an algorithm and its initial input, we determine if the algorithm when executed in this input will ever stop/halt. If it does not halt, it runs forever in an infinite loop.

Table of contents.

1. Introduction.
2. Proving the halting problem.
3. Reduction and consequences.
4. Summary.
5. References.

Introduction.

In computability theory we describe the halting problem as follows;
Given an algorithm and its initial input, we determine if the algorithm when executed in this input will ever stop/halt. If it does not halt, it runs forever in an infinite loop.

Computability theory - This is a branch of a theory that studies problems that can be solved computationally by a different model.

Decision problem - A decision has two outcomes, a yes or a no given any input. It is posed as a yes-no question on input values.

The halting problem depends on what type of algorithms we are considering. This problem in turing machines is undecidable. Conversely, on finite state automata, the halting problem is decidable since all finite-state automata halt. And therefore it is important to specify a model.

Proving the halting problem.

We intend to answer and prove our answer. The question is, Given an algorithm, will it halt of loop infinitely?

For halting, the program either accepts and halts or rejects the input and halts, otherwise, it loops infinitely.

So can we design such a program that determines if another program halts or terminates? The answer is NO. We have to run this program and check whether it halts or not. In other terms, given an algorithm written in a high-level programming language such as Java/C++, is there a way to know if it halts or loops infinitely.

This is an undecidable problem since we can't have such an algorithm. We can't always know therefore we cannot have a generalized algorithm. The best we can do is to execute the actual program to determine if it halts or not.

Proof by contradiction.

The question remains the same. The following is the proof:

Proof:
Assuming we can design such an algorithm / turing machine - T(P, I) where T is the machine or algorithm, P is the program, and I is the input.
Given the input, we will know if a program P halts or loops infinitely. If designing such an algorithm is possible, we create another program Q(X) where X is any program.

We have the following;

In Q(X), we call a function T(X) and pass arguments X and X. This is because T can take two arguments. The first is the program, the second is the input.
In the second program, we pass X as a program and X as input. We know T can result in either halt or a no halt.
In the second program when T(X, X), halts the loop body, it tells the program to go in the loop and when it doesn't halt, the loop continues infinitely.

In another case where the program Q is passed as an argument, the outer function can't halt if its code is in the loop. Also, the outer function can't halt even if its inner code halts.

In both cases Q is non-halting.

This is a contradiction and so we say that our previous assumption was wrong and conclude that the halting problem is undecidable.

Reduction and consequences.

A common way to prove that a problem is undecidable is to reduce it to the halting problem. If it is reducible then it is undecidable otherwise it is not.

Formally we say that a problem A is reducible to problem B if a solution to B can solve A. If it has been proved that A is undecidable, then to prove that B is also undecidable it is enough to show that a solution to B can be used to decide A.

This results in a contradiction since we proved that A is undecidable, therefore B is also undecidable.

Summary.

The halting problem begs the question: Is there a computer program that can examine a piece of code and determine if the program will terminate?

An answer to this is NO, this is because if there was such a program we could run it on another version itself that halts when it determines the other program does not stop and runs an infinite loop if it determines that the other program stop. This is a contradiction we have proved through reductio ad absurdum.
The halting problem is undecidable.

With this article at OpenGenus, you must have the complete idea of The Halting problem.