Get the latest tech news
Scooping the Loop Snooper (2000)
SCOOPING THE LOOP SNOOPER A proof that the Halting Problem is undecidable Geoffrey K. Pullum (School of Philosophy, Psychology and Language Sciences, University of Edinburgh) An earlier version of this poetic proof was published in Mathematics Magazine (73, no.
I will prove that although you might work till you drop, you cannot tell if computation will stop.For imagine we have a procedure called P that for specified input permits you to see whether specified source code, with all of its faults, defines a routine that eventually halts.You feed in your program, with suitable data, and P gets to work, and a little while later (in finite compute time) correctly infers whether infinite looping behavior occurs. I’ll define a procedure, which I will call Q, that will use P ’s predictions of halting success to stir up a terrible logical mess. I’ve created a paradox, neat as can be — and simply by using your putative P. When you posited P you stepped into a snare; Your assumption has led you right into my lair.
Or read this on Hacker News