{"id":1085,"date":"2010-09-12T21:21:58","date_gmt":"2010-09-12T21:21:58","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/?p=1085"},"modified":"2010-09-12T21:21:58","modified_gmt":"2010-09-12T21:21:58","slug":"the-halting-problem","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2010\/09\/12\/the-halting-problem\/","title":{"rendered":"The Halting Problem"},"content":{"rendered":"

Some people expressed interest in seeing a full-out, formal presentation of the Halting problem proof. So, I’m going to walk through it. There are actually a lot of different versions of this proof; the one that I’m going to use is based on the one used by my grad-school theory professor, Dr. John Case. To be clear, I’m doing it from memory, so any errors are completely my own fault, not John’s!<\/p>\n

To start off, we need to define what a computing device is. In formal mathematical terms, we don’t care how it works – all we care about is what it can do in abstract tems. So what we do is define something called an effective computing device<\/em>. An effective computing device is any Turing equivalent computing device. An ECS is modelled as a two parameter function phi : {cal N} times {cal N} rightarrow {cal N}. The first parameter is an encoding of a program as a natural number; the second parameter is the input to the program. It’s also a natural number, which might seem limiting – but we can encode any finite data structure as an integer, so it’s really not a problem. The return value is the result of the program, if the program halts. If it doesn’t halt, then we say that the pair of program and input aren’t in the domain of phi. So if you wanted to describe running the program “f” on the input 7, you’d write that as phi(f, 7). And, finally, the way that we would write that a program p doesn’t halt for input i as phi(p, i) = bot.<\/p>\n

So now we’ve got our basic effective computing device. There’s one thing we still need before we can formulate the halting problem. We need to be able to deal with more parameters. After all – a halting oracle is a program that takes two inputs – another program, snd the input to that program. the easiest way to do that is to use something called a pairing function<\/em>. A pairing functions is a one-to-one function from an ordered pair to an integer. There are lots of possible pairing functions – for example, you can convert both numbers to binary, left-pad the smaller until they’re equal length, and then interleave the bits. Given (9,3), you convert 9 to 1001, and 3 to 11; then you pad 3 to 0011, and interleave them to give you 10001011 – 139. We’ll write our pairing function as angle brackets around the two values: langle x,yrangle.<\/p>\n

With the help of the pairing function, we can now express the halting problem. The question is, does there exist a program O, called a halting oracle, such that:<\/p>\n

forall p, forall i: (varphi(O,langle p,irangle) = left{ begin{array}{l}\t0 mbox{ if } varphi(p, i) = bot \\\t1 mbox{ if } varphi(p,i) neq bot end{array}right.<\/center><\/p>\n

In english, does there exist a program O such that for all pairs of programs p and inputs i, the oracle returns 1 if varphi(p, i) halts, and 0 if it doesn’t?<\/p>\n

Time, finally, for the proof. Suppose that we do<\/em> have a halting oracle, O. That means that for any program p and input i, varphi(O, langle p, i rangle) = 0 iff varphi(p,i)=bot.<\/p>\n

So, can we devise a program $p_d$ and input i where varphi(p_d, i) != bot,
\nbut varphi(O, langle p, i rangle) = 0? <\/p>\n

Of course we can. We need a p_d which takes two parameters: an oracle, and an input. So it should be really simple right? Well, not quite as easy as it might seem. You see, the problem is, p_d needs to be able to pass itself<\/em> to the oracle. But how can it do that? A program can’t pass itself<\/em> into the oracle. Why not? Because we’re working with the program as a Gödel number – and a program can’t contain its own Gödel number. If it contained it, it would be larger than itself. And that’s rather a problem.<\/p>\n

But there’s a nice workaround. What we care about is: is there any combination<\/em> of program and input<\/em> such that O will incorrectly predict the halting status? So what we’ll do is just turn p_d into a parameter to itself. That is, we’ll look at a program p_d like the following:<\/p>\n

\ndef deceiver(input):\n   (oracle, program) =  unpair(input)\n   if oracle(program, input):\n      while(True): continue\n   else:\n      halt\n<\/pre>\n
 Then we’ll be interested in the case where the value of the program<\/code> parameter is a Gödel number of the deceiver itself<\/em>.<\/p>\n
 (As an aside, there are a variety of tricks to work around this. One of the more classical ones is based on the fact that for any given program, p, there are an infinite<\/em> number of versions of the same program with different Gödel numbers. Using that property, you can embed a program p_{d_2} into another program p_{d}. But there are a few other tricks involved in getting it right. It’s not simple – Alan Turing screwed it up in the first published version of the proof!)<\/p>\n
 Now, when input = langle O, p_d rangle, then O will make the wrong<\/em> prediction about what p_d will do. So – once again, we’re back where we were in the simpler version of the proof. A halting oracle is a program which, given any<\/em> pair of program and input, will correctly determine whether that program will halt on that input. We’re able to construct a pair of program and input where the oracle doesn’t<\/em> make the right prediction, and therefore, it isn’t<\/em> a halting oracle.<\/p>\n
 This version is more abstract, but it’s still got that wonderfully concrete property. Even in the most abstract way of talking about a computing device, if you’ve got something that you believe is a halting oracle, this shows you how to create a program that will prove that the halting oracle is wrong<\/em>. So you can’t possibly create a halting oracle.<\/p>\n
 And to be extra clear: this doesn’t rely on any ambiguities about definitions, or any distinction between values and meanings. It shows a way of producing a real, concrete counterexample for any purported halting oracle. No trickery, no fudging –  if you think you have a halting oracle, you’re wrong, and this proof shows you exactly how to create a program that will demonstrate that.<\/p>\n","protected":false},"excerpt":{"rendered":"
Some people expressed interest in seeing a full-out, formal presentation of the Halting problem proof. So, I’m going to walk through it. There are actually a lot of different versions of this proof; the one that I’m going to use is based on the one used by my grad-school theory professor, Dr. John Case. To […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"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":[79],"tags":[],"class_list":["post-1085","post","type-post","status-publish","format-standard","hentry","category-computation"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-hv","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/1085","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=1085"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/1085\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=1085"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=1085"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=1085"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}