A few minutes ago, a good friend of mine recommended me this brief piece of poetry. I thought I’d share it here. It did make me smile.<\/p>\n
SCOOPING THE LOOP SNOOPER<\/p>\n
A proof that the Halting Problem is undecidable<\/p>\n
Geoffrey K. Pullum<\/p>\n
(School of Philosophy, Psychology and Language Sciences, University of Edinburgh)<\/p>\n
No general procedure for bug checks succeeds.
\nNow, I won\u2019t just assert that, I\u2019ll show where it leads:
\nI will prove that although you might work till you drop,
\nyou cannot tell if computation will stop.<\/p>\n
For imagine we have a procedure called P
\nthat for specified input permits you to see
\nwhether specified source code, with all of its faults,
\ndefines a routine that eventually halts.<\/p>\n
You feed in your program, with suitable data,
\nand P gets to work, and a little while later
\n(in finite compute time) correctly infers
\nwhether infinite looping behavior occurs.<\/p>\n
If there will be no looping, then P prints out `Good.\u2019
\nThat means work on this input will halt, as it should.
\nBut if it detects an unstoppable loop,
\nthen P reports `Bad!\u2019 \u2014 which means you\u2019re in the soup.<\/p>\n
Well, the truth is that P cannot possibly be,
\nbecause if you wrote it and gave it to me,
\nI could use it to set up a logical bind
\nthat would shatter your reason and scramble your mind.<\/p>\n
Here\u2019s the trick that I\u2019ll use \u2014 and it\u2019s simple to do.
\nI\u2019ll define a procedure, which I will call Q,
\nthat will use P\u2019s predictions of halting success
\nto stir up a terrible logical mess.<\/p>\n
For a specified program, say A, one supplies,
\nthe first step of this program called Q I devise
\nis to find out from P what\u2019s the right thing to say
\nof the looping behavior of A run on A.<\/p>\n
If P\u2019s answer is `Bad!\u2019, Q will suddenly stop.
\nBut otherwise, Q will go back to the top,
\nand start off again, looping endlessly back,
\ntill the universe dies and turns frozen and black.<\/p>\n
And this program called Q wouldn\u2019t stay on the shelf;
\nI would ask it to forecast its run on itself.
\nWhen it reads its own source code, just what will it do?
\nWhat\u2019s the looping behavior of Q run on Q?<\/p>\n
If P warns of infinite loops, Q will quit;
\nyet P is supposed to speak truly of it!
\nAnd if Q\u2019s going to quit, then P should say `Good\u2019
\n\u2014 which makes Q start to loop! (P denied that it would.)<\/p>\n
No matter how P might perform, Q will scoop it:
\nQ uses P\u2019s output to make P look stupid.
\nWhatever P says, it cannot predict Q:
\nP is right when it\u2019s wrong, and is false when it\u2019s true!<\/p>\n
I\u2019ve created a paradox, neat as can be \u2014
\nand simply by using your putative P.
\nWhen you posited P you stepped into a snare;
\nYour assumption has led you right into my lair.<\/p>\n
So where can this argument possibly go?
\nI don\u2019t have to tell you; I\u2019m sure you must know.
\nBy reductio, there cannot possibly be
\na procedure that acts like the mythical P.<\/p>\n
You can never find general mechanical means
\nfor predicting the acts of computing machines.
\nIt\u2019s something that cannot be done. So we users
\nmust find our own bugs. Our computers are losers!<\/p>\n","protected":false},"excerpt":{"rendered":"
A few minutes ago, a good friend of mine recommended me this brief piece of poetry. I thought I’d share it here. It did make me smile. 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) No general procedure for bug checks succeeds. Now, …<\/p>\n","protected":false},"author":312,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ngg_post_thumbnail":0,"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[33311],"tags":[422990,422991,91118],"class_list":["post-606","post","type-post","status-publish","format-standard","hentry","category-southampton-university-life","tag-poetry","tag-pullum","tag-smile","column","twocol"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p3BSCk-9M","_links":{"self":[{"href":"https:\/\/blog.soton.ac.uk\/studentblogs\/wp-json\/wp\/v2\/posts\/606","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.soton.ac.uk\/studentblogs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.soton.ac.uk\/studentblogs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.soton.ac.uk\/studentblogs\/wp-json\/wp\/v2\/users\/312"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.soton.ac.uk\/studentblogs\/wp-json\/wp\/v2\/comments?post=606"}],"version-history":[{"count":2,"href":"https:\/\/blog.soton.ac.uk\/studentblogs\/wp-json\/wp\/v2\/posts\/606\/revisions"}],"predecessor-version":[{"id":911,"href":"https:\/\/blog.soton.ac.uk\/studentblogs\/wp-json\/wp\/v2\/posts\/606\/revisions\/911"}],"wp:attachment":[{"href":"https:\/\/blog.soton.ac.uk\/studentblogs\/wp-json\/wp\/v2\/media?parent=606"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.soton.ac.uk\/studentblogs\/wp-json\/wp\/v2\/categories?post=606"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.soton.ac.uk\/studentblogs\/wp-json\/wp\/v2\/tags?post=606"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}