Sunday, December 30, 2007

Computable numbers paradox

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.