Re: Cantor Diagonal Proof

On 4/8/25 7:48 PM, Keith Thompson wrote:

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.

It is at least related, and there are a number of theories that all tie together here, really hinging on the fact that the countable infinite concept spans the gap between finiteness and infiniteness.

 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.

Since there are only a countable number of machines that could compute numbers, there must be no more than a countable infinity of such numbers.
The diagonalization doesn't give us a computable number, as the diagonalization uses an operation that isn't "computable", namely select the algorithm for the nth number on the list. (or at least that operation isn't computable if there are an infinite number of numbers on the list).
It does show that there can't be a finite number of computable numbers, but there are simpler ways to prove that.

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

THAT isn't a true statement. I resently saw a demonstration of how with the Axiom of Choice, we can create an uncountably long list of the Real Numbers, All the non-rational numbers get pairs to ordinal like 5 omega + 12, but the list can be made. It just isn't countable.

 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.)

Again, I don't think that holds. an ordered list of the computable numbers exists (in fact an infinite number of them), we just may not be able to compute that list. Strangely, we

 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.
 

They aren't, at least not if you accept the axiom of choice, which is part of the normal basis for the counting numbers.