tag:blogger.com,1999:blog-2811876938195306723.post1865119672488336896..comments2023-07-07T01:27:13.382-07:00Comments on Absolutely Regular: Computable numbers paradoxAryehhttp://www.blogger.com/profile/14913393383227385317noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-2811876938195306723.post-8025980154530783762008-10-02T16:32:00.004-07:002008-10-02T16:32:00.004-07:00This comment has been removed by the author.Aryehhttps://www.blogger.com/profile/14913393383227385317noreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-12264443184886516362008-10-02T16:32:00.003-07:002008-10-02T16:32:00.003-07:00This comment has been removed by the author.Aryehhttps://www.blogger.com/profile/14913393383227385317noreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-34135196356500121332008-10-02T16:32:00.000-07:002008-10-02T16:32:00.000-07:00This comment has been removed by the author.Aryehhttps://www.blogger.com/profile/14913393383227385317noreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-57467345910108342852008-08-04T15:10:00.000-07:002008-08-04T15:10:00.000-07:00Thanks fo the historical note, Giovanni!Thanks fo the historical note, Giovanni!Aryehhttps://www.blogger.com/profile/14913393383227385317noreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-48784529381419493052008-08-02T21:05:00.000-07:002008-08-02T21:05:00.000-07:00This fallacious argument appears in the paper "On ...This fallacious argument appears in the paper "On computable numbers, with an application to the Entscheidungsproblem", by Alan Turing, dated 1936. Turing uses it as an example of a wrong application of the diagonal process. Since that's precisely the first paper in which the definition of 'computable number' is given, I'm reasonably sure the true author of this paradox is Turing himself.<BR/>Regards, GVAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-79698350738435025472008-02-25T12:26:00.000-08:002008-02-25T12:26:00.000-08:00Anonymous: Rob's argument shows that one of our or...Anonymous: Rob's argument shows that one of our original assumptions was wrong--indeed, it is a proof that what Noam said is true. Of course we could also fairly easily give a proof by reduction to the halting problem, or simply by appealing to <A HREF="http://en.wikipedia.org/wiki/Rice%27s_theorem" REL="nofollow">Rice's Theorem</A>. However, what Rob said about where the flaw lies is not quite right--Cantor diagonalization *is* a well-defined, constructive, algorithmic process as long as we know the machines produce digits. Indeed, if we have an R.E. sequence of Turing machines which output digits, then we can diagonalize and get a sequence which was not listed in the original list.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-42960018030697003962008-01-11T17:22:00.000-08:002008-01-11T17:22:00.000-08:00I do not see how Rob's argument "explains" the par...I do not see how Rob's argument "explains" the paradox. Of course we know r is not computable. Robs argument just gives another contradiction if we assume r is computable. The real meat in the paradox comes because of the assumption that the set of computable reals is computably enumerable. To me Noam's argument seems to drive the point home better.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-58672078202994573912008-01-09T03:16:00.000-08:002008-01-09T03:16:00.000-08:00Regarding the historical note in the last comment ...Regarding the historical note in the last comment -- yes, I was being sloppy in my attribution. Sylvain is a topologist, not a computer scientists -- and certainly did come up with it on his own. He related it to me over a Saturday Kiddush (when no writing or computers are allowed) and I resolved it, pretty much along the lines of Noam's argument, in a matter of minutes. As Noam points out, the "paradox" is pretty much anticipated in the Wikipedia article, and almost certainly goes back to the earliest days of computability theory. I'm still quite partial to Rob's very slick direct proof!Aryehhttps://www.blogger.com/profile/14913393383227385317noreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-16997166695497323492008-01-08T22:50:00.000-08:002008-01-08T22:50:00.000-08:00This is indeed a great paradox, but I don't think ...This is indeed a great paradox, but I don't think it's a fair historical description to say it is "due to Sylvain Cappell". He may have rediscovered it, but I suspect it was known in this form before he was born, and certainly before he graduated from college (1966).<BR/><BR/>The earliest reference I could find on my shelf is Minsky's 1967 book "Computation: Finite and Infinite Machines" (pages 160-162). He doesn't present it initially as a paradox, but he explicitly describes how to prove that the computable reals are countable, how to prove that they are not computably enumerable, and why the latter proof doesn't actually show uncountability although it might at first appear to (which is the paradox). I bet it goes back far earlier than Minsky, and has been rediscovered many times over the years. I've also heard it from other sources in the form of a paradox, although I can't rule out the possibility that Cappell was the first person to present it that way.<BR/><BR/>One amusing rediscovery is by a crank at http://descmath.com/diag/namable.html. It is phrased in terms of which numbers can be named, rather than computed, but it is the same idea. However, the author regards it as evidence that the very concept of countability is ill-defined. It's sad to see someone apply apparently genuine mathematical talent to crankery.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-60290177339346673732008-01-01T11:38:00.000-08:002008-01-01T11:38:00.000-08:00Nicely done, Rob and Noam -- you guys really kille...Nicely done, Rob and Noam -- you guys really killed that one. Of course r is not computable from general principles, but I really liked Rob's slick self-contained proof. Again, I wish I'd known of this "paradox" when I was TAing the automata course...Aryehhttps://www.blogger.com/profile/14913393383227385317noreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-46060118875987484012007-12-31T08:31:00.000-08:002007-12-31T08:31:00.000-08:00It actually gives the answer to this paradox in th...It actually gives the answer to this paradox in the wikipedia article: although the computable reals are countable, they are not <A HREF="http://en.wikipedia.org/wiki/Computably_enumerable" REL="nofollow">computably enumerable</A>. The intuitive reason why is that computable reals don't correspond to <I>arbitrary</I> Turing machines, but to ones that eventually terminate giving you the nth digit, for every input n. Hence there is no way to effectively generate the list T, and r is not computable.Noamhttps://www.blogger.com/profile/09175792123472366590noreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-43605704472892460402007-12-31T00:47:00.000-08:002007-12-31T00:47:00.000-08:00r is not computable. I believe the error in reaso...r is not computable. I believe the error in reasoning is here.<BR/><BR/><I>Cantor diagonalization is a well-defined, constructive, algorithmic process -- so constructing r out of T should be a cinch.</I><BR/><BR/>Proof: r is not computable. By contradiction.<BR/><BR/>Assume without loss of generality the diagonalization maps 4 to 5, and all other numbers to 4.<BR/><BR/>Since r is computable, there must be some turing machine that computes it. Let k be the index of the first such turing machine. Then what is at index (k, k)? If (k, k) is 4, then by definition of the diagonal, (k, k) should be 5. Otherwise, (k, k) is not 4, and hence (k, k) must be 4. Thus, we have our contradiction.rrenaudhttps://www.blogger.com/profile/00268587839942674447noreply@blogger.com