I would like to raise some questions about the proof that I was
given as an undergraduate that the real numbers are not countable. This
(usually called Cantor's diagonalization proof) is roughly:-
  Suppose the real numbers are countable.  Then they can all be written
  in a single list.  We now generate a new number not in the list thus
  contradicting the premise that all real numbers are in the list.  Each
  number in the list has a decimal representation.  Generate the new number
  by writing a '4' for the n th digit if the n th digit of the b th number
  in the list is not '4' and '3' otherwise.  The new number is not in the
  list since it differs from the n th number in the n th digit.  Thus it
  is not possible to produce such a list and so the totality of real
  numbers is not countable.

T think that this argument has several flaws.  (please note, I don't
dispute the conclusion that the reals are not countable, only the
validity of this particular 'proof'.)

A real number is defined by a Dedekind section that divides the rationals
into U and L classes.  Each real number thus depends on an algorithm
to divide the rationals: one can think of it as the condition that the
number satisfies.  Each of these algorithms can be defined; if you want
to be really precise, define it as a Turing machine.  All these algorithms
can be ordered; by length and alphabetically among algorithms of the
same length.

The procedure given above for computing the new number is an algorithm
like this.  It therefore has a position in the list say N.  What is its
N th digit? If its '3' it must be '4' and if it's '4' it must be '3'!

The most obvious solution to the dilema is to say that the procedure is
not a valid one to apply to this set.  However, if it isn't a valid
algorithm it can't be used to generate a number not in the list.

Let me put this argument another way.  Cantor's procedure is a way to
compute a number.  The number it generates must be a 'computable number.'
However, the set of computable numbers is countable, and so if we apply
Cantor's procedure to the set of all computable numbers we get a paradox:
the number must be in the list because it it computable but cannot be in
the n th position for any n since it differs from it in the n th digit.

 There might well be different models of the number systems such that
the reals in one model are countable in the other model.

 If your argument is just that Cantor's procedure is not computable, since
it relies on the axiom of choice, this is well known.

Basically, you wind up proving that if the set of computable numbers is
countable, then it's countable.  Leastways, that's what it looks like to
me.

Did I miss anything?  How silly do I sound?

There are, in fact, only countably many computable reals.  Your
paradox arises from the fact that even though there is a canonical
listing of turing machines which lists all such (reals), there's an
important subtlety: not all of the computations in this list converge
everywhere.  This leads to an escape from the paradox you propose.

Let us take the rule which computes the "Cantor computable rule."
It's got an index in the list---say 17.  Aha! we say, let's go look at
the 17th digit of the seventeenth element.  We turn the computer on,
sit down with a pizza, and wait for the machine to finish.

We finish the pizza, and it's still not done.  So we order another
pizza, finish *it*...and the computation still isn't finished.  In
fact, we would wait forever and still never find out what happens.
The process described does not ever complete; it's an infinite
regress:

compute the seventeenth digit of r_17,
  compute the seventeenth digit of r_17,
    compute the seventeenth digit of r_17,
    .
    .
    .
    take its complement
  take its complement
take its complement

But the tower is infinitely deep, and we never start to pop the stack.
So the paradox is resolved by virtue of the fact the there is no value
to complement.

In fact, this is a sketch of the proof of a famous lemma of Kleene's
(and, yes, I know that I'm invoking Church's thesis in this statement,
so don't send me mail telling me so):

Lemma: If L is any computable function from NxN to N which contains
the graphs of all total computable functions from N to N as sections,
then L is not total: there is some pair (n, m) on which the
computation which defines L does not converge.

One obvious corollary of this statement is the Second Incompleteness
Theorem, which is why this is such an important lemma.  In fact, this
is the first proof of the SIT that I ever learned; the more standard
proof never really made sense to me until after I understood this one.

You have not discovered a flaw in Cantor's diagonal argument, but you are
halfway to discovering the modification of Cantor's diagonal argument that
yields a number of classic results in computability theory and mathematical
logic.  Goedel, Turing, Church and Kleene all played a role in exploring
this new territory in the '30s and '40s; I remember reading somewhere that
Kleene was at one point puzzled by essentially the same point you bring up
(except in the context of Church's lambda-calculus), and found the
resolution of the paradox one of the most satisfying discoveries of his
career.

By the way, Cantor's diagonal argument does not depend on the axiom of
choice, despite what one of the replies to your post stated.

I think it's easier to explore these topics with decimal sequences, rather
than Dedekind sections (granted we can easily associate a Dedekind section
with each decimal sequence in some standardized way.)  I'm also going to
ignore the whole .10000... = .099999...  problem, because it's an annoyance
that has nothing to do with the fundamental mathematics involved.  Let's
just say we're interested in the set of all infinite sequences of decimal digits, so
that (1,0,0,...) and (0,9,9,...) are distinct.

Consider two sets:

        S: the set of all infinite decimal sequences.

        S-comp: the set of all computable infinite decimal sequences; that
                is, for each sequence in this set, there must be an
                algorithm that produces the successive digits.

If we have a sequence of elements of S, say P1, P2, ..., then Cantor's
argument shows how to construct a sequence Q of digits (i.e., Q is an
element of S) such that Q is not equal to any of the P's.  Hence S is not
countable.

The puzzle you bring up arises from trying to apply the same argument to
S-comp.  S-comp is clearly countable.  Applying the diagonal argument to
S-comp yields a sequence Q that is not in S-comp.  On the other hand, it
would seem that we have an algorithm for computing the successive digits of
Q, as you point out.  Doesn't this mean that Q is in S-comp?

To resolve the paradox, we have to look more closely at how the listing of
all algorithms yields a listing of all elements of S-comp.  As you note, we
can list Turing programs in order of length, and alphabetically within a
given length.

The problem is, not all programs give algorithms that specify an infinite
sequence of digits.  A program may get into an infinite loop computing,
say, the 777-th digit, and never produce any digits after that.  Call this
a "bad" program.

There is no computable way of eliminating the bad programs-- that is, there
is no algorithm for determining which programs are bad.  If there were,
then Q would indeed be a computable sequence, and we would have a real
contradiction on our hands!  This is the nugget that comes from your
puzzle.

Variations on this theme yield:

        the undecidability of the halting problem
        Kleene's second recursion theorem
        Tarski's theorem on the undefinability of truth
        Goedel's incompleteness theorem

and much more.  See, for example, "Goedel, Escher, Bach", by Douglas
Hofstadter, "Theory of Recursive Functions", by Hartley Rogers, and any
book on mathematical logic.

I should note that the above discussion is the version accepted by most
mathematicians today, i.e., anyone whose philosophy of mathematics is
Platonist, formalist, or
I-don't-worry-about-these-things-I-just-prove-theorems.  I don't know what
the intuitionist position on these matters is.

A quote from, I believe, Andre Weil:

        We know God exists, because Mathematics is consistent; we know the
        Devil exists, because we cannot prove it.

I don't know the source for this quote:

I would say that the real flaw in this argument is just in the phrase "... it
would seem that we have an algorithm for computing the successive digits of Q,
..".  I assume the suggested algorithm is

i := 0;
loop
        compute the i-th digit of sequence i;
        change this digit and output it;
        i := i + 1;
end loop;

But this "algorithm" references all the (infinite number of) algorithms of
S-comp in the line "compute the i-th digit...".  Thus it is in fact itself
infinite, that is, not an algorithm at all.  So this argument does not show Q
to be computable.

I will give an example of a non-computable real number N:
Lets order all Turing machines: T_1, T_2, T_3, etc. Then define
N as the real number with decimal representation
0.{a_1}{a_2}{a_3}{a_4}  ....
where a_i is equal to 0 iff T_i halts and equal to 1 iff T_i does
not halt. If N were a computable real number in any reasonable
sense, then the halting problem could be solved.

The fact, that the decimal representation of the reals is not a
unique one (think of 0.999999999.... = 1.00000000 ) and is not
the preferred approach to the reals for a rigorous view does not
threaten my argument but just makes it more easy to write down.

Definition:

     A decimal representation for a real number will be called TERMINATING if
     it contains a finite number of non-zero digits, and NON-TERMINATING
     otherwise.

Here are some illustrative examples:

     1.000....  contains 1 non-zero digit and is therefore TERMINATING.
     0.999....  contains an infinite number of non-zero digits and is
                therefore NON-TERMINATING.
     0.5000.... is TERMINATING.
     0.4999.... is NON-TERMINATING.

I offer my sincere thanks to Neil W. Rickert for drawing my attention to
this potential source of confusion.

Fred Chapman