tag:blogger.com,1999:blog-7068528325708136131.post6657181336778652062..comments2017-04-21T10:34:21.489-07:00Comments on Structural insight: Computation and truthJohn Shutthttp://www.blogger.com/profile/00041398073010099077noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-7068528325708136131.post-3764137683809974882017-04-15T19:18:48.486-07:002017-04-15T19:18:48.486-07:00Of course, the argument is identical if we conside...Of course, the argument is identical if we consider that L* i is not contained in A but is part of its input. The same machine, A, fed the same input, A + L^ 1, gives different results in different L^i.Enrique Pérez Arnaudhttp://www.blogger.com/profile/13443099473984173421noreply@blogger.comtag:blogger.com,1999:blog-7068528325708136131.post-53967515747517787892017-04-15T17:13:25.455-07:002017-04-15T17:13:25.455-07:00This comes from a discussion at Lambda the ultimat...This comes from a discussion at Lambda the ultimate, answering this comment [1]-<br /><br />In your rendition of Gödel's incompleteness theorem, you speak about a Turing machine L and another A.<br /><br />the machine A must obviously contain L.<br />No problem with that. Let's note it with A(L)<br /><br />L is about implementation, in the sense that to be able to, given some machine f, determine that it produces some output, either you run the machine, or you already have within L all possible results of all possible machines, which is crazy.<br /><br />So L corresponds with a given way to encode Turing machines and run them.<br /><br />There are many, many ways of doing this (Encoding and running Turing machines). Let's note this by adding an index to L, L^i. It's totally harmless, and we can still have L^1, that is exactly and simply L, by<br />definition here and now.<br /><br />However now we also have different A(L^i), and also A(L^1).<br /><br />In your text, we may say that you encode A(L^1) in L^1 and feed it to A(L^1).<br />And this produces a contradiction.<br /><br />But using indexes allows us to wonder:<br /><br />What happens if we encode the A(L^1) in L^2 and feed it to the A(L^2) machine?<br />It will find no trouble at all, no contradiction.<br />And feeding it to A(L^2) amounts to nothing but running it;<br />So, running the Turing machine A(L^1) in different environments leads to different<br />results. The results are implementation dependent.<br /><br />Expressing the same Turing machine, A(L^1), in 2 different encodings, L^1 and L^2, leads to different results.<br /><br />1.- http://lambda-the-ultimate.org/node/5425#comment-94109Enrique Pérez Arnaudhttp://www.blogger.com/profile/13443099473984173421noreply@blogger.comtag:blogger.com,1999:blog-7068528325708136131.post-90467453700950844792017-04-15T17:10:53.934-07:002017-04-15T17:10:53.934-07:00This comment has been removed by the author.Enrique Pérez Arnaudhttp://www.blogger.com/profile/13443099473984173421noreply@blogger.comtag:blogger.com,1999:blog-7068528325708136131.post-20477339774971290502015-05-15T14:16:23.749-07:002015-05-15T14:16:23.749-07:00This description of Godel's incompleteness the...This description of Godel's incompleteness theorem is similar to other traditional accounts in that it misses an important fact: according to Godel's *completeness* theorem (a result much more fundamental than the celebrated incompleteness one) a sentence is provable iff it is valid in all models. This means that the "Godel's sentence", which is unprovable in PA, is necessary invalid in some versions of natural numbers.<br /><br />Of course, up to this day, there is no shortage of people who believe that there is only one true set of natural numbers (sanctioned by the Pope and Congress, presumably) and that their Turing machines compute functions on this sacred object.furia-kruchahttp://furia-krucha.livejournal.com/noreply@blogger.com