tag:blogger.com,1999:blog-7068528325708136131.post6657181336778652062..comments2022-05-11T10:58:17.480-07:00Comments on Structural insight: Computation and truthJohn Shutthttp://www.blogger.com/profile/00041398073010099077noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-7068528325708136131.post-28567062712958928562017-06-30T05:44:58.253-07:002017-06-30T05:44:58.253-07:00For the diagonalization method, what's importa...For the diagonalization method, what's important about the diagonal is that for every row of the table, there is *at least* one entry in that row that's identical to the diagonal: for the nth row, its nth entry is identical to the nth entry on the diagonal (that's how we define what we mean by "the diagonal"). It doesn't matter if some row also has other entries in common with the diagonal, as long as it has at least one. If we can construct a row that differs in every entry from the diagonal, it cannot be the nth row in the table for *any n*. For a typical diagonalization proof that the halting problem is undecidable, there is in fact some row of the table that's identical to the diagonal, because it's possible to construct a Turing machine that for the nth input generates the nth entry of the diagonal, and since that Turing machine exists it must appear as a row of the table.John Shutthttps://www.blogger.com/profile/00041398073010099077noreply@blogger.comtag:blogger.com,1999:blog-7068528325708136131.post-48111379033146064542017-06-29T23:16:22.255-07:002017-06-29T23:16:22.255-07:00Question about diagonalization: How do you prove t...Question about diagonalization: How do you prove the diagonal does not occur as a single 'line' entry in the table? Surely it could occur? For example a table where every line is 123456789, would have a diagonal that is 123456789?Anonymoushttps://www.blogger.com/profile/02907358636234277429noreply@blogger.comtag: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 Arnaudhttps://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 Arnaudhttps://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 Arnaudhttps://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.Anonymousnoreply@blogger.com