| Version 6 |
Version 5 |
| \PMlinkescapeword{loop} |
\PMlinkescapeword{loop} |
|
|
| The \emph{halting problem} is to determine, given a particular input to a particular computer program, whether the program will terminate after a finite number of steps. |
The \emph{halting problem} is to determine, given a particular input to a particular computer program, whether the program will terminate after a finite number of steps. |
|
|
| The consequences of a solution to the halting problem are far-reaching. Consider some predicate $P(x)$ regarding natural numbers; suppose we conjecture that $P(x)$ holds for all $x \in \mathbb{N}$. (Goldbach's conjecture, for example, takes this form.) We can write a program that will count up through the natural numbers and terminate upon finding some $n$ such that $P(n)$ is false; if the conjecture holds in general, then our program will never terminate. Then, \emph{without running the program}, we could pass it along to a halting program to prove or disprove the conjecture. |
The consequences of a solution to the halting problem are far-reaching. Consider some predicate $P(x)$ regarding natural numbers; suppose we conjecture that $P(x)$ holds for all $x \in \mathbb{N}$. (Goldbach's conjecture, for example, takes this form.) We can write a program that will count up through the natural numbers and terminate upon finding some $n$ such that $P(n)$ is false; if the conjecture holds in general, then our program will never terminate. Then, \emph{without running the program}, we could pass it along to a halting program to prove or disprove the conjecture. |
|
|
| In 1936, Alan Turing proved that the halting problem is undecideable; the argument is presented here informally. Consider a hypothetical program that decides the halting the problem: |
In 1936, Alan Turing proved that the halting problem is undecideable; the argument is presented here informally. Consider a hypothetical program that decides the halting the problem: |
|
|
| \begin{Lalgorithm}{Halt}{P, I}{A computer program $P$ and some input $I$ for $P$}{True if $P$ halts on $I$ and false otherwise} |
\begin{Lalgorithm}{Halt}{P, I}{A computer program $P$ and some input $I$ for $P$}{True if $P$ halts on $I$ and false otherwise} |
| \end{Lalgorithm} |
\end{Lalgorithm} |
|
|
| The implementation of the algorithm, as it turns out, is irrelevant. Now consider another program: |
The implementation of the algorithm, as it turns out, is irrelevant. Now consider another program: |
|
|
|
\begin{Lalgorithm}{Break}{x}{Code $x$}{}
|
\begin{Lalgorithm}{Break}{x}{An irrelevant parameter $x$}{}
|
| \Lgroup{ |
\Lgroup{ |
|
\Lif{IsValidCode(x)} and {Halt(x,x)}{\Lwhile{true}{nothing}}
|
\Lif{$Halt(Break,x)$}{\Lwhile{true}{nothing}}
|
|
\Lelse{ return true }
|
\Lelse{ $Break \gets true$ }
|
| } |
} |
|
|
| \end{Lalgorithm} |
\end{Lalgorithm} |
|
|
|
If our halting solution determines that Break(Break) halts, then it will immediately enter an infinite loop; otherwise, Break will return immediately. We must conclude that the Halt program does not decide the halting problem.
|
If our halting solution determines that Break halts, then it will immediately enter an infinite loop; otherwise, Break will return immediately. We must conclude that the Halt program does not decide the halting problem.
|
| So for any attempted solution to the halting problem, we can find some input which breaks that solution. |
So for any attempted solution to the halting problem, we can find some input which breaks that solution. |
