Here's a delicious paradox, due to Sylvain Cappell. Consider the class of the computable real numbers -- i.e., those reals for which there is a Turing machine that is guaranteed to produce the nth decimal digit in finite time. This is a well-defined and countable subset of the reals; let's denote it by T.
Being countable, the elements of T may be enumerated and arranged in an array of digits where the (i,j)th entry is the jth digit in the expansion of the ith element of T. You can probably guess what's coming next -- we're going to apply Cantor diagonalization to this list and obtain a new real number r, not in T.
It seems we have a nasty paradox on our hands. On the one hand, Cantor diagonalization is a well-defined, constructive, algorithmic process -- so constructing r out of T should be a cinch. On the other hand, by assumption, T is an exhaustive list of all the computable numbers -- so r should not be computable. So which is it -- is r computable or not?
Discussion is welcome in the comments. I'll close by that I would've loved to use this question on my automata theory undergrads.
Update: I was being sloppy in attribution; please see comments.
Subscribe to:
Post Comments (Atom)
12 comments:
r is not computable. I believe the error in reasoning is here.
Cantor diagonalization is a well-defined, constructive, algorithmic process -- so constructing r out of T should be a cinch.
Proof: r is not computable. By contradiction.
Assume without loss of generality the diagonalization maps 4 to 5, and all other numbers to 4.
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.
It actually gives the answer to this paradox in the wikipedia article: although the computable reals are countable, they are not computably enumerable. The intuitive reason why is that computable reals don't correspond to arbitrary 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.
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...
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).
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.
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.
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!
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.
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 Rice's Theorem. 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.
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.
Regards, GV
Thanks fo the historical note, Giovanni!
Post a Comment