{"id":199,"date":"2015-05-09T02:29:14","date_gmt":"2015-05-09T02:29:14","guid":{"rendered":"http:\/\/aristotle2digital.blogwyrm.com\/?p=199"},"modified":"2015-05-09T02:29:14","modified_gmt":"2015-05-09T02:29:14","slug":"turing-godel-and-the-universe","status":"publish","type":"post","link":"https:\/\/aristotle2digital.blogwyrm.com\/?p=199","title":{"rendered":"Turing, G\u00f6del, and the Universe"},"content":{"rendered":"

Something about the book \u2018Five Golden Rules: Great Theories of 20th<\/sup>-Century Mathematics and Why They Matter\u2019 by John L. Casti caught my eye the other day at the library.\u00a0 On a whim, I signed the book out and started reading.\u00a0 Living up to the promise of the title, the book had five chapters, each one devoted to one of the great math theories of 20th<\/sup> century.\u00a0 All in all, I had been exposed, at least superficially, to all the topics covered so I wasn\u2019t sure what I would get out of the book other than some additional insight into material I already knew or confirmation of my wisdom in staying away from topics that I didn\u2019t.<\/p>\n

Anyway, I am quite glad that the mechanism of providence pointed me at this book because the connections that Casti draws are worth thinking about.\u00a0 None of these connections was as profound for me as the deep link that he explores in Chapter 4 entitled \u2018The Halting Theorem (Theory of Computation)\u2019.<\/p>\n

In this chapter, Casti first presents the concept of the universal Turing machine (UTM) as a mechanism for attacking the question of Decision Problem (or Entscheidungsproblem)<\/a> proposed by David Hilbert in 1928.\u00a0 Casti then couples this presentation with a discussion of the famous G\u00f6del Incompleteness Theorem<\/a>.<\/p>\n

I\u2019m simply a beginner in these fields and Casti omits important details and glosses over a variety of things to help the novice.\u00a0 From this point-of-view, I can\u2019t recommend his work.\u00a0 But I am grateful and excited about the perspective he provided by making this linkage.<\/p>\n

To understand my excitement, let me first try to fill in some of the background as best as I can.<\/p>\n

Hilbert\u2019s Decision Problem asks the following question.\u00a0 Given a set of input data and an algorithm for manipulating said data, is there a way to know if the algorithm will be able to make a yes\/no decision about the input.\u00a0 For example, if the input data is a set of axioms in a logical system and some corresponding assertion in the same system and the algorithm is a logical formalism, such as the classical syllogism, will the algorithm be able to prove or disprove the assertion as either true (yes) or false (no)?<\/p>\n

While the Decision Problem might seem straightforward enough to talk about it at a seminar, when it comes to actually tackling the question there are some vague conceptions that need further elaboration.\u00a0 Specifically, what does the term \u2018algorithm\u2019 really mean and what constitutes a workable algorithm seem to have been the murkiest part when the problem was first posed.<\/p>\n

Turing chose to clarify the algorithm concept by the invention of the machine which bears his name.\u00a0 The UTM is a basic model of computation that is often used to understand the theory behind computer programming. It is also the avenue that allowed Turing to a way to tackle Hilbert\u2019s Decision Problem.\u00a0 The basic ingredients for a UTM are a tape or strip of paper, divided into squares, a set of symbols (usually \u20180\u2019 and \u20181\u2019) that can be written into the squares, and a box that has a mechanism for moving the strip left or right, a head that reads from and writes to the strip and that contains an internal state that allows the UTM to select an action from a pre-defined set, given the internal state and current symbol being read.\u00a0 A typical graphical representation of an UTM looks like<\/p>\n

\"Turing_machine\"<\/a><\/p>\n

The UTM can represent the input to the decision process by a particular pattern of symbols on the strip.\u00a0 It can also implement the step associated with an algorithm by encoding these also to symbols on the tape.\u00a0 So the entire nature of the Decision Problem comes down to the question as to whether once the UTM starts if it will ever halt; hence the name of the name of the chapter.<\/p>\n

Kurt G\u00f6del took a different approach to answering the Decision Problem.\u00a0 He developed a way to map any formal system to a set of numbers, called G\u00f6del numbers.\u00a0 Then by formally manipulating these numbers, he was in position to try to answer Hilbert\u2019s challenge.<\/p>\n

Now it is reasonable to suppose that all not every question has a yes or no answer.\u00a0 Questions about feeling, opinion, or taste spring to mind.\u00a0 But I think that most of us expect that questions of mathematics and logic and programming have answers and that we should be able to figure them out.\u00a0 The remarkable thing about the work of both Turing and G\u00f6del is that there are cases where the formal logical system simply can\u2019t decide.<\/p>\n

In the language of Turing, there are computational problems for which there is no knowing beforehand if the algorithm will terminate with an answer.\u00a0 In the language of G\u00f6del, no matter is done to a logical system in terms of refining existing axioms or adopting new ones, there will always be truths that are unprovable.<\/p>\n

I was quite aware of Godel\u2019s theorem and even wrestled with it for a while when I was concerned about its implications to physical systems.\u00a0 Eventually, I decided that while man\u2019s logic may be limited, nature didn\u2019t need to worry about it because she could make decisions unencumbered by our shortcomings.<\/p>\n

I was also quite aware that Turing\u2019s machine was used fruitfully as a model computation.\u00a0 What I was unaware of until reading Casti\u2019s book was the parallel between the conclusions of G\u00f6del and of Turing.<\/p>\n

And here we arrive at the source of my excitement.\u00a0 As I\u2019ve already said, I remain convinced that Nature can decide \u2013 that is to say that Nature is free of the issues discussed above.\u00a0 And yet, in some capacity the Universe is an enormous Turing machine.<\/p>\n

\"Universe_as_Turing\"<\/a><\/p>\n

So why does Nature always make a decision and why does the computation of trajectories, and the motion of waves, and evolution of quantum bit of stuff always reach a decision? \u00a0It may not be the decision we expect or anticipate, but it seems clear that a decision is reached. \u00a0And so, by looking at how the Universe as a Turing Machine (UaaTM) differs from a Universal Turing Machine, one may learn more about both. \u00a0This is the exciting new idea that has occurred to me and one which I will be exploring in the coming months.<\/p>\n","protected":false},"excerpt":{"rendered":"

Something about the book \u2018Five Golden Rules: Great Theories of 20th-Century Mathematics and Why They Matter\u2019 by John L. Casti caught my eye the other day at the library.\u00a0 On… Read more ><\/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-199","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts\/199","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=199"}],"version-history":[{"count":0,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts\/199\/revisions"}],"wp:attachment":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=199"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=199"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=199"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}