Re: Cantor Diagonal Proof

On 09/04/2025 00:48, 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.

For most maths people, "lists" and "sequences" mean the same.  "List" is an everyday word, so they may say "list" when explaining to non-maths people, and "sequence" in maths discussions.  [Also "list" used for finite sequences perhaps.]
I haven't seen "list" used with the deliberately different meaning of "computable sequence", which is how you appear to think of the term - or at least that seems consistent with my reading of what you write below.
So I would say this is the key to what you wonder you might be missing.
If you treat (infinite) lists and sequences as meaning the same thing, they are just functions mapping N [natural numbers] to the target set.  No reason for sequences to be computable in the mathematical sense (based on TM definitions).  A sequence can be uncomputable even if the elements of the sequence are computable objects (e.g. computable numbers).
This makes some of your statements below incorrect if using normal terminology, although it seems to me that you perfectly understand the issues involved.  (So I'd recommend just a change in perspective/terminology.)

 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.

Alternatively, it can apply to /any/ list of real numbers, and shows that there is a real missing from that list.  [So in particular there cannot exist any /complete/ list of real numbers.]

 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.

Right, those are examples of the alternative interpretation of the proof I gave above.
What you said applies to /any/ countable set of real numbers, such as the rationals, algebraic numbers or the computable real numbers.  Saying an infinite set is countable means there is a bijection from N to the set, i.e. it's the same as saying it can be "listed".  And the diagonal argument shows there is a real number not in that list (so not in the original countable set).

 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.

This is where you seem to conflate "list" with "computable list/sequence".  Or perhaps the issue is your idea behind "generating" a list(?).  In mathematics, functions don't need to be physically/mechanically generated or computed.
The normal maths way of putting all this is that the set of computable numbers is countable (can be "listed" / there exists a one-to-one mapping from N to the computable numbers), and when the diagonal argument is applied it results (as above) in a non-computable number that's (obviously) not in the list.
So the outstanding mystery to understand is /why/ isn't the list computable?
Each number in the list is computable, so there is a finite procedure to generate digits /for that number/.  But each number in the list has its /own/ finite procedure that is used for that number. Taken together there are infinitely many such finite procedures...
In order to think of "the Cantor diagonalisation procedure" as a form of TM computation of digits, that TM needs to be able to generate the n'th digit of the n'th number in the list, FOR EVERY n.
One might imagine simply merging all the (infinitely many) individual finite digit-generating procedures for all the numbers in the list, into one super-digit-generating procedure - but that will not work because there is no such super-procedure that can be coded in a finite number of states.  Someone claiming otherwise would need to define this merging process that produces the finite super-procedure, and of course nobody does that.
Perhaps we imagine there might be some computable means of enumerating the TM descriptions for all computable numbers, then a single TM could simulate them succesively to produce the n'th digit of the n'th number in the list?  That fails for the exact reason you explain below which ties in with the halting theorem / Rice's theorem.  We can effectively enumerate all TM descriptions, but there is no computable way to then filter only the TMs associated with computable numbers.
Or perhaps we think the list itself can be fed in as data to the super-procedure?  That's obviously not allowed as the list contains an infinite amount of data and we demand a finite process.
So I'd say you understand the problem, but use the terminology "not in the usual way"...

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

Yep.  (In Cantor's one-to-one correspondence sense.)

 There is no list of computable numbers, but for a different reason.

There is such a list (i.e. the computable numbers are countable).
There is no /computable/ list (which would allow a single TM to generate the m'th digit of the n'th list entry).  The term "effectively list" and "effective procedure to list" are also used in the literature meaning more or less the same thing.

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.
 

Yeah, that's the point I would make - I don't think mathematicians generally use "list" as explicitly meaning "computable list/sequence", and also you talk about "generating" lists, but that terminology also suggest lists must be mechanically produced somehow, which is not how the term is normally used.
The fact that the TMs corresponding to computable numbers /can't/ be "effectively listed" in the sense we've talked about is actually proved by the argument given above - if they could, then the anti-diagonal number for the list /would/ be computable, so the anti-diagonal would be in the list and also not in the list: contradiction.  That may sound circular for someone who just believes they /can/ be effectively listed and that they've proved Cantor was wrong etc. - but of course such a person has the responsibility of mathematically defining the required global list procedure.  It is not enough to just keep stating that "it can be done with finite input" without backing that up!
Mike.