## You are here

Homehalting problem

## Primary tabs

# halting problem

The *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, *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:

Algorithm Halt(P, I)

Input: A computer program $P$ and some input $I$ for $P$

Output: True if $P$ halts on $I$ and false otherwise

The implementation of the algorithm, as it turns out, is irrelevant. Now consider another program:

Algorithm Break(x)

Input: Code $x$

Output:

begin

if IsValidCode(x) and Halt(x,x) then

while true do

nothing

else

return true

end

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. So for any attempted solution to the halting problem, we can find some input which breaks that solution.

## Mathematics Subject Classification

03D75*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## Decidability

I love decidability proofs. This sentence is false.

## Self reference

I think the proof glosses over the crucial part: How can Break refer to itself within Break's definition?

You need to use Goedel's trick somehow: first construct an algorithm B that stops if and only if its argument, interpreted as an algorithm, won't stop on its own description, and then feed the description of B to B itself.

Akin to the barber (B) who shaves everybody who doesn't shave himself. Ask whether B shaves B and it blows up.

## Re: Self reference

This is true, but in this particular case it's not really a problem to gloss over the fact. Goedel's trick in this context is: find a way to encode an algorithm as a string of data that an algorithm can process. But this is exact what programming languages do. Running "Halt" on the encoded form of "Break" is not a diificult opertaion to visualize.

Of course, for a full proof, you're quite right. But if one is willing to accept that, say, Scheme is Turing-complete (easy to demonstrate: just write a Turing machine simlator) the proof is relatively straightforward.

## Re: Self reference

To elaborate:

The current Break algorithm reads:

Break(x) {

if Halt(Break,x) then

while true do nothing

else

return true

fi

}

modify it to:

Break(x) {

if IsValidCode(x) and Halt(x,x) then

while true do nothing

else

return true

fi

}

This no longer references itself. Let Break be some encoding of the

program Break(x). Consider Break(Break). IsValidCode(Break) is certainly true. Now if Halt(Break,Break) is true then Break(Break) gets stuck in the while loop, so doesn't halt. If Halt(Break,Break) is false, then the if branches to the return true statement and the Break(Break) halts after all. Thus the given program Halt(x,y) is not a solution to the halting problem (since it gives the wrong result for the particular case of Break given above.)

## Re: Self reference

"Running "Halt" on the encoded form of "Break" is not a diificult opertaion to visualize."

True, but programming "Break" in the first place is extremely hard to visualize. After all, the programm "Break" contains within it a representation of the program "Break"! It's not clear how to write something like that in Scheme, for instance.

Please change Break(x) in the way suggested by John Allsup below.

Break(x) {

if IsValidCode(x) and Halt(x,x) then

while true do nothing

else

return true

fi

}