The Halting Problem

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 the Halting 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:

\[  \mbox{\textbf{HALT}(program,input)}=\left\{  \begin{tabular}{l}\mbox{Output YES, if the program does halt on the input,}

\\ \mbox{Output NO, otherwise. } 

\end{tabular}  \]

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:

\[  \mbox{\textbf{OPPOSITE}(program)}=\left\{  \begin{tabular}{l}\mbox{Halt, if \textbf{HALT}(program, program) returns NO, }

\\ \mbox{Loop forever, otherwise. } 

\end{tabular}  \]

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.

“It is one of the first examples of a decision problem.”

I have included a video by Computerphile which I think describes the problem and proof very well:

M x

Advertisements

One comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s