Halting Problem

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. For any program f that might determine if programs halt, a "pathological" program g called with an input can pass its own source and its input to f and then specifically do the opposite of what f predicts g will do. No f can exist that handles this case. A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine; the halting problem is undecidable over Turing machines. Turing's proof is one of the first cases of decision problems to be concluded. The theoretical conclusion that it is not solvable is significant to practical computing efforts, defining a class of applications which no programming invention can possibly perform perfectly.

Halting problem is undecidable

Proof by contradiction

Assume we have a procedure HALTS that takes as input a program P and input data D and answers yes if P halts on input D and no otherwise.

Of course we can't just have HALTS simulate P on input D, since if P doesn't halt, we'll never know exactly when to quit the simulation and answer no.

Since there are no assumptions about the type of inputs we expect, the input D to a program P could itself be a program. Compilers and editors both take programs as inputs.

Given a Pascal compiler written in Pascal, we might want to know if the compiler halts when given itself as input.

Given the program HALTS, we can construct a new (more limited) program that tests whether a program P halts when the input data is a copy of P.

      procedure NEWHALTS(P);
      if HALTS(P,P) then writeln('Yes');
      else writeln('No');

Given NEWHALTS, we can construct another program that does just the opposite of NEWHALTS:

      procedure OPP(P);
      if NEWHALTS(P) outputs 'Yes' then
          loop forever
      else halt;
     
What happens when we call OPP(OPP)?

Inside OPP, we call NEWHALTS(OPP), which calls HALTS(OPP,OPP). If OPP halts when fed OPP as input then the call OPP(OPP)loops forever.

If OPP doesn't halt when fed OPP as input, then the call OPP(OPP) halts.

OPP(OPP) can neither halt nor loop forever.

This is a contradiction! Since our only assumption was the existence of HALTS, procedure HALTS cannot exist.

https://youtu.be/macM_MtS_w4

Suhaib Bin Younis | @suhaibbinyounis