To understand the process of computation, regardless of the technology available, we need to reduce it to its most basic elements. One way to model computation is to consider an input, operated on by a program which produces some output.

In 1936, Alan Turing constructed such a model and considered the question of determining whether a program will finish running or will continue to run forever i.e. halt. This is known as theHalting Problem.

Let us suppose that we write a program, let’s call it HALT, that, given another program and its associated input, can determine whether running that program with the input will halt or not. This can be represented in the following way:

Note that we do not have to consider how this program works, it is merely sufficient to assume that there does exist such a program. Now, consider a new program, call it OPPOSITE which does the opposite of halt. In other words, it analyses programs running with themselves as the input, acting in the following way:

Now, what happens when we run OPPOSITE on itself?

If OPPOSITE(opposite) halts, then it must loop forever, but if it loops forever then it must halt. Hence, there is a contradiction, highlighting how the program HALT cannot exist.

This was an incredible result. Firstly, in this proof a computer and a program were mathematically defined, paving the way to the creation of the Turing Machines. Furthermore, Turing had found a program whose existence is logically impossible, and showed that knowing whether a program halts on some input is undecidable.

Hilbert’s Tenth problem (which you discussed in earlier blog post) can be restated as a Halting problem.

LikeLiked by 2 people