{"id":480,"date":"2016-03-18T23:30:49","date_gmt":"2016-03-19T03:30:49","guid":{"rendered":"http:\/\/aristotle2digital.blogwyrm.com\/?p=480"},"modified":"2016-03-12T19:36:03","modified_gmt":"2016-03-13T00:36:03","slug":"bare-bones-halting","status":"publish","type":"post","link":"https:\/\/aristotle2digital.blogwyrm.com\/?p=480","title":{"rendered":"Bare Bones Halting"},"content":{"rendered":"<p>It\u2019s a rare thing to find a clear and simple explanation for something complicated \u2013 something like the Pythagorean Theorem or calculus or whatnot.\u00a0 It\u2019s even rarer to find a clear and simple explanation for something that challenges the very pillars of logic \u2013 something like G\u00f6del\u2019s Theorem or the halting theorem.\u00a0 But J. Glenn Brookshear treats readers of his text <em>Computer Science: An Overview<\/em> to a remarkably clear exploration of the halting theorem in just a scant 3 pages in Chapter 12. I found this explanation so easy to digest that I thought I would devote a post to it, expanding on it in certain spots and putting my own spin on it.<\/p>\n<p>Now to manage some expectations:\u00a0 it is important to note that this proof is not rigorous; many technical details needed to precisely define terms are swept under the rug; but neither is it incorrect.\u00a0 It is logically sound if a bit on the heuristic side.<\/p>\n<p>The halting theorem is important in computer science and logic because it proves that it is impossible to construct an algorithm that is able to analyze an arbitrary computer program and all its possible inputs and determine if the program will run to a successful completion (i.e. halt) or will run forever, being unable to reach a solution.\u00a0 The implications of this theorem are profound since its proof demonstrates that some functions are not computable and I\u2019ve discussed some of these notions in <a href=\"http:\/\/aristotle2digital.blogwyrm.com\/?s=Halting&amp;searchsubmit.x=0&amp;searchsubmit.y=0\">previous posts<\/a>.\u00a0 This will be the first time I\u2019ve set down a general notion of its proof.<\/p>\n<p>The basic elements of the proof are a universal programing language, which Brookshear calls Bare Bones, and the basic idea of self-referential analysis.<\/p>\n<p>The Bare Bones language is a sort of universal pseudocode to express those computable functions that run on a <a href=\"http:\/\/aristotle2digital.blogwyrm.com\/?p=199\">Turing Machine<\/a> (called Turing-computable functions).\u00a0 The language, which is very simple, has three assignment commands:<\/p>\n<ul>\n<li>Clear a variable<\/li>\n<li>Increment a variable<\/li>\n<li>Decrement a variable<\/li>\n<\/ul>\n<p>In addition, there is one looping construct based on the while loop that looks like<\/p>\n<div class=\"myQuoteDiv\">\n<pre>while x not 0 do;\r\n   ...\r\nend;<\/pre>\n<\/div>\n<p>While primitive, these commands make it possible to produce any type of higher level function.\u00a0 For \u00a0example, Brookshear provides an algorithm for computing the product of two positive integers:<\/p>\n<p><a href=\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/BB-Multiply.png\" rel=\"attachment wp-att-479\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-479\" src=\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/BB-Multiply.png\" alt=\"BB Multiply\" width=\"449\" height=\"740\" srcset=\"https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/BB-Multiply.png 449w, https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/BB-Multiply-182x300.png 182w\" sizes=\"auto, (max-width: 449px) 100vw, 449px\" \/><\/a><\/p>\n<p><em>Note:<\/em> for simplicity only positive integers will be discussed \u2013 but the results generalize to any type of computer word (float, sign int, etc.).<\/p>\n<p>Now Bare Bones is a universal language in the sense that researchers have demonstrated that all Turing-computable functions can be expressed as Bare Bones algorithms similar to the Multiply function shown above.\u00a0 Assuming the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Church%E2%80%93Turing_thesis\">Church-Turing thesis<\/a>, which states that the set of all computable functions is the same as the set of all Turing-computable functions, allows one to conclude that Bare Bones is sufficiently rich to encode all algorithms that express computable functions.<\/p>\n<p>One particularly important Bare Bones algorithm is something I call x-test (since Brookshear doesn\u2019t give it a name).<\/p>\n<p><a href=\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/x-test.png\" rel=\"attachment wp-att-478\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-478\" src=\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/x-test.png\" alt=\"x-test\" width=\"428\" height=\"216\" srcset=\"https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/x-test.png 428w, https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/x-test-300x151.png 300w\" sizes=\"auto, (max-width: 428px) 100vw, 428px\" \/><\/a><\/p>\n<p>The job of x-test is simple: it either terminates when x is identically zero or it runs forever otherwise.<\/p>\n<p><a href=\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/x-test-at-work.png\" rel=\"attachment wp-att-477\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-477\" src=\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/x-test-at-work.png\" alt=\"x-test at work\" width=\"999\" height=\"754\" srcset=\"https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/x-test-at-work.png 999w, https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/x-test-at-work-300x226.png 300w, https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/x-test-at-work-768x580.png 768w, https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/x-test-at-work-810x611.png 810w\" sizes=\"auto, (max-width: 999px) 100vw, 999px\" \/><\/a><\/p>\n<p>The Terminate flag is assigned a value of 0 if x-test fails to halt and 1 if it does.<\/p>\n<p>The next step brings in the concept of self-reference.\u00a0 The function x-test takes an arbitrary integer in and gives the binary output or 0 or 1.\u00a0 Since x-test is expressed as a set of characters in Bare Bones and since each character can be associated with an integer, the entire expression of x-test can be associated with an integer.\u00a0 To be concrete, the string representation of x-test is:<\/p>\n<div class=\"&quot;myQuoteDiv\">\n<pre>\u2018while x not 0 do;\\n\u00a0\u00a0\u00a0 increment x;\\nend;\u2019\r\n<\/pre>\n<\/div>\n<p>A simple python program, called <strong>string_to_int<\/strong>:<\/p>\n<div class=\"&quot;myQuoteDiv\">\n<pre>def string_to_int(s):\r\n    ord3 = lambda x : '%.3d' % ord(x)\r\n    return int(''.join(map(ord3, s)))\r\n<\/pre>\n<\/div>\n<p>transforms this string to the (very long) integer<\/p>\n<div class=\"&quot;myQuoteDiv\">\n<pre>119104105108101032120032110111116032048032100111059010032032032032105110099114101109101110116032120059010101110100059\r\n<\/pre>\n<\/div>\n<p>Using this integer in x-test results in the Terminate flag equal 0.<\/p>\n<p>Of course, any expression of x-test in any programming language will result in a nonzero integer and so x-test never has a chance to terminate.<\/p>\n<p><a href=\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/xtest-is-not-self-terminating.png\" rel=\"attachment wp-att-476\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-476\" src=\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/xtest-is-not-self-terminating.png\" alt=\"xtest is not self-terminating\" width=\"1228\" height=\"967\" srcset=\"https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/xtest-is-not-self-terminating.png 1228w, https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/xtest-is-not-self-terminating-300x236.png 300w, https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/xtest-is-not-self-terminating-768x605.png 768w, https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/xtest-is-not-self-terminating-1024x806.png 1024w, https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/xtest-is-not-self-terminating-810x638.png 810w\" sizes=\"auto, (max-width: 1228px) 100vw, 1228px\" \/><\/a><\/p>\n<p>But there are clearly functions that do terminate when they are expressed as input for their own execution (one obvious example is the duel function to x-test where the while loop stops if x is non-zero).\u00a0 Such functions are said to be self-terminating.<\/p>\n<p>Although it may look like a lot of effort for nothing, this notion of self-terminating functions is the key to the halting theorem and all that remains is to combine the above results with some clever thinking.<\/p>\n<p>The clever thinking starts with the assumption that there exists a function, which I call the Hypothetical Halting Program (HHP), that can analyze any arbitrary program written in Bare Bones along with any corresponding input and determine which combinations will terminate (decidable) and which will not (undecidable).<\/p>\n<p>Again, to be concrete, let\u2019s look at what the HHP would do when looking to see if x-test is self-terminating.<\/p>\n<p><a href=\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/HHP-analyzes-xtest.png\" rel=\"attachment wp-att-475\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-475\" src=\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/HHP-analyzes-xtest.png\" alt=\"HHP analyzes xtest\" width=\"1216\" height=\"967\" srcset=\"https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/HHP-analyzes-xtest.png 1216w, https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/HHP-analyzes-xtest-300x239.png 300w, https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/HHP-analyzes-xtest-768x611.png 768w, https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/HHP-analyzes-xtest-1024x814.png 1024w, https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/HHP-analyzes-xtest-810x644.png 810w\" sizes=\"auto, (max-width: 1216px) 100vw, 1216px\" \/><\/a><\/p>\n<p>The HHP would be given the x-test function and the corresponding input (x-test in integer form) and would determine, just as we did above, that x-test won\u2019t terminate \u2013 that is, x-test is not self-terminating.<\/p>\n<p>Now such a function that works only on x-test is easy to understand; the text above that argued against x-test being self-terminating is one such instantiation.\u00a0 However, the goal is to have the HHP be abale to analyze all such algorithms so that we don\u2019t have to think.\u00a0 Already, warning bells should be going off, since the word \u2018all\u2019 is a pretty big set, in fact infinite, and infinite sets have a habit of behaving badly.<\/p>\n<p>But let\u2019s set aside that concern for the moment and just continue our assumption that HHP can do the job.\u00a0 As we progress, we\u2019ll see that our assumption of the existence of the HHP will lead to a contradiction that rules out this assumption and, thus, gives the desired proof.\u00a0 Operating without this foresight, we argue that since the HHP is computable it must be able to find expression as a Bare Bones program.\u00a0 And since the HHP analyzes Bare Bones programs, it must be able to analyze itself and determine if it is self-terminating \u2013 spitting out a 1 if so and a 0 otherwise.<\/p>\n<p>Now we can construct a new program, called the HHP++, that is the sequential running of the HHP followed by x-test.<\/p>\n<p><a href=\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/HPP.png\" rel=\"attachment wp-att-474\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-474\" src=\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/HPP.png\" alt=\"HPP++\" width=\"428\" height=\"450\" srcset=\"https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/HPP.png 428w, https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/HPP-285x300.png 285w\" sizes=\"auto, (max-width: 428px) 100vw, 428px\" \/><\/a><\/p>\n<p>We can always do this in Bare Bones by first running HHP and then assigning its output (0 or 1) to the input of x-test.\u00a0 And here is where it gets interesting.<\/p>\n<p>Take the HHP++ and let it test itself to see if it is self-terminating.\u00a0 If it is self-terminating, the HHP piece will confirm it so and will output a value of 1.\u00a0 This value is then passed to the x-test piece which then falls to halt.\u00a0 If the HHP++ is not self-terminating, the HHP piece will output a 0 which, when passed to the x-test piece, halts the operation.\u00a0 Thus the HHP++ is a program that is neither self-terminating nor not self-terminating and so the only way that can be true is that our original assumption that the HHP exists is false.<\/p>\n<p><a href=\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/HPP-contradiction.png\" rel=\"attachment wp-att-482\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-482\" src=\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/HPP-contradiction.png\" alt=\"HPP++ contradiction\" width=\"857\" height=\"737\" srcset=\"https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/HPP-contradiction.png 857w, https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/HPP-contradiction-300x258.png 300w, https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/HPP-contradiction-768x660.png 768w, https:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/03\/HPP-contradiction-810x697.png 810w\" sizes=\"auto, (max-width: 857px) 100vw, 857px\" \/><\/a><\/p>\n<p>It is remarkable that using such a simple argument, the human mind is able to rule out the possibility of general function like the HHP.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>It\u2019s a rare thing to find a clear and simple explanation for something complicated \u2013 something like the Pythagorean Theorem or calculus or whatnot.\u00a0 It\u2019s even rarer to find a&#8230; <a class=\"read-more-button\" href=\"https:\/\/aristotle2digital.blogwyrm.com\/?p=480\">Read more &gt;<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-480","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts\/480","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=480"}],"version-history":[{"count":0,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts\/480\/revisions"}],"wp:attachment":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=480"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=480"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=480"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}