Halting problem

From Uncyclopedia, the content-free encyclopedia.

The halting problem is the difficulty computer scientists have experienced with shutting up and doing something useful. 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.

[edit] Proof the halting problem exists

Alan Turing proved the existence of the halting problem using this shockingly elegant argument:

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 contrapositive).
5. An entity cannot undertake the task of deciding halting for all algorithms (from 3, 4).
6. The halting problem is undecided 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!

[edit] 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.

[edit] 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

[edit] Implications

[edit] Speeding tickets

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

Vehicles with onboard computers are continuously failing to stop at stop signs or before falling off cliffs. This is due to the fact that 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 looses control of a frozen car, it goes on the lose and takes years to track down, racking up trillions of speeding tickets. The driver is so poor from the parking tickets she declares bankruptcy, and can only ever afford one of the faulty automobiles. The cycle begins anew.

[edit] Humanity

Terrorists are working on exposing the internal functionings of the human mind as a kind of algorithm. This will mean that 1/3 of the Earth's population that has not already been Fucking Killed by Steve Ballmer could freeze in masturbation or spongebath mode. Oh, the... humanity, yes.

[edit] The Song that probably never ends

"Some people starting singing it not knowing its halting problem 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.

[edit] 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, and Steve Ballmer can't be everywhere at once. A little-known fact is that for every computer program written and distributed, 1 to 392 computers must sit running faulty versions of it until the end of time. They cannot be destroyed even by the best efforts of the magic ring. Those computers get expensive, and Windows requires 4 GB disk space; a compromise had to be reached.