Halting problem

		It is requested that an image or images be included in this article to improve its quality. If possible, please add some pictures to make it into a full encyclopedia article and then remove this message. Do not remove this notice until it receives some pictures. Failure to comply will result in this notice being added again.

The halting problem is the difficulty computer scientists have experienced with shutting up and doing something useful. Many are quite content with trying to solve programs that are "really really hard" , or trying to prove that said problems area in fact "really really hard" or if there is some "not-so-hard" way to solve them. One example of such a problem is determining whether P = NP (which is in fact true when N = 1). The halting problem is also one of these problems. More recently, some have erroneously applied the term to the chatbots and other programs that computer scientists write to take the flak for them and let them shirk their duties plowing the fields.

Proof the halting problem exists

Alan Turing proved attempted the existence of the halting problem in 1936 by constructing a universal Turing machine. Unfortunately, the first attempt failed due to some of the tape jamming in the machine and the machine halting without accepting or rejecting the input. The solution was to construct another Turing machine, this one capable of simulating the first. Ultimately this one ran out tape, and Turing was unable to obtain enough tape required to complete the computation. He then went for the next best alternative - by constructing a Turing machine that used a large loop of tape (the loop is in fact endless, so it is still a valid Turing machine). This machine continued to run, but he could not determine if or when it would halt. He concluded that:

1. There exist an infinite number of possible algorithms (by Schizt-Flingher's conjecture).
2. There exists a one-to-one bijection between an algorithm and the fact of whether it stops sometime.
3. There exists an infinite amount of halting information (from 1, 2).
4. An entity may not have infinite knowledge (your head a splode contra-positive).
5. An entity cannot undertake the task of deciding halting for all algorithms (from 3, 4).
6. The halting problem is undecidable for all algorithms (from 5).
7. A subset of a closed set has the properties of the whole set (by fallacy of division).
8. For any algorithm you select, you will be unable to determine if it stops (from the choice axiom and 6, 7).

The last step is contingent on what choice axiom one chooses. This startling result shows that no accurate prediction can be made about whether an algorithm will ever finish!

Example

for ( i=k; i<q; i+=n ) {

kill_kenny( episode_number:i ) ;

}

No one can know k, q, n for this algorithm (or the type declaration of i for that matter). No, you can't. Hence, this halting problem is undecidable. The above algorithm is famous, as it proved empirically not to halt, and hence resulted in the death of Kenny every episode - even in the episodes that haven't been made yet.

Common misinterpretations

A common failure in understanding by computer science students is to think that the halting problem can be solved by mathematical induction. They usually suggest an approach like f(1), f(2), f(3), f(4) to satisfy themselves that the algorithm halts. Unfortunately, the rules of induction state that no matter what value of n you use as a trial upper bound in f(n), f(n+1) could possibly run forever. Plus you didn't try 1.5, did you? Did you?!

“Input the value 'spij' and you're on thin ice. Input 'poink' and you could be screwed.”

~ Albert Einstein on Halting problem

Implications

Dating

The principle can be applied to real life. A good example is asking someone out on a date. There are three possible outcomes. They may halt and accept the invitation or halt and reject it. As anyone who has ever tried to date will tell you, the third (and most common) outcome is that they never get back to you. Nor can we determine if they get back to you many years into the future. By Murphy's Law and Rice's Theorem, even if one asks an infinite number of people, we cannot decide if anyone will halt and accept their request to go on a date. Given an infinite amount of time, one person may get back to you, but there are no guarantees.

Speeding tickets

A common, but futile, attempt to make computer-controlled vehicles stop.

Vehicles with on-board computers are continuously failing to stop at stop signs. This is because even though one halting problem was empirically tested, technically new Automatic Breaking System inputs generate virtual functions on the fly. ABS has since been discontinued. Unfortunately, when a driver loses control of such a car, it goes wild, racking up thousands in speeding tickets. Ultimately, the car will eventually halt once it runs out of fuel, but if the car were powered by solar power or a fusion reactor, it will continue to run until it crashes. There is no way to determine when it will crash, if it even does at all. Where the car will crash or not is undecidable.

The Song that probably never ends

"Some people starting singing it not knowing that was undecidable, and now they'll be singing it forever just because it's the SONG THAT PROBABLY NEVER ENDS; it's non-computable my friends~~. ~~Some people starting singing..."

Hours of grappling were required to terminate the song at that point. Phew.

Computer technology

The undecidability of the halting problem gives Microsoft a perfectly valid excuse for its terribly shoddy software. Once an application is run, it can never be terminated as you can't kill an abstract idea. There are three outcomes to any computer operation.

1. Halt and accept - that is the operation completes successfully
2. Halt and reject - the operation will complete, but will have errors, such as the Blue Screen of Death
3. Continue without halting - some operations will not halt immediately and there is no way to determine whether it will halt or not. A good example is the spinning beach ball on Macintosh based systems.

Literature

Although considered mostly harmless by the Hitchhiker's Guide to the Galaxy, Planet Earth was constructed as a computer (as it is capable of simulating a Turing machine) to calculate the Ultimate Question. The calculation was never completed due to the Vogon's destruction of the planet. While the program would have probably completed had the Earth not been destroyed, there was still an infinitely improbable chance that it would run forever if it had been allowed to. As a result, we cannot determine if the program would halt or not.

See also

• Infinite Loop