Re: Cantor Diagonal Proof

Richard Damon <richard@damon-family.org> writes:
[...]

And from what I see, the issue is that while each of the numbers in
the list could be defined as constructable, in that a algorithm exists
that given n, it will give at least n digits of that number, there
doesn't need to be a master algorithm, that given k and n gives the
first n digits of the kth number, that can be shown to cover the full
set of constructable numbers (but perhaps an countable infinite subset
of them). Without that master algorithm, the method of constructing
the diagonal isn't actually an implementable algorithm.
>
We can't just iterate through all possible machines, because not all
machines are halting, let alone meet the requirements for the
construction machines.
>
Thus, we don't have an actual algorithm that makes the diagonal number
constructable.

So it's the Halting Problem that makes it impossible to computationally
generate a list of all computable numbers, even though there are only a
countable infinity of them.

Cantor's proof applies correctly to the real numbers.  Given a purported
infinite list of all the real numbers, we can construct a real number
that's not in the list; therefore there is no such list.

The same proof does not apply to rational numbers.  We can generate an
infinite list of all the rational numbers, and the diagonal construction
demonstrates the existence of a number that's not on the list, but any
such number is not rational, so there's no contradiction.  Same thing
for algebraic numbers.  The rational and algebraic numbers *can* be
placed into a one-to-one mapping with the integers.

There are only a countable infinity of computable numbers (right?),
but if I understand correctly the halting problem prevents us
from generating a list of them.  Given a purported list of all the
computable numbers, diagonalization gives us a computable number
that's not in the list.

There is no list of real numbers because there are strictly more real
numbers than integers.

There is no list of computable numbers, but for a different reason.
There are *not* strictly more computable numbers than integers,
but the halting problem makes it impossible to construct a list
of them.  (Generate an ordered list of all possible algorithms in
some notation.  Eliminate the ones that don't generate a computable
number.  But we can't perform the elimination step because it would
require solving the halting problem.)

It feels intuitively weird that there is a set of numbers that is
countably infinite but we can't generate an ordered list of them.
But sometimes math is like that.

I suspect I'm still missing something.  For one thing, I'm not
sure whether "we can't computationally generate the list" and "the
list doesn't exist" are equivalent statements.

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */