Re: Cantor Diagonal Proof

On 10/04/2025 02:06, Lawrence D'Oliveiro wrote:

On Wed, 9 Apr 2025 18:49:54 +0100, Mike Terry wrote:
 

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.

If you would like me to comment on your suggestions below, we'll need to start by clarifying what you mean exactly.  That bit shouldn't take long, but given that your final conclusion below is obvious nonsense, you might consider it a waste of time...

 Assume the list consists of algorithms for all computable numbers which
are guaranteed to terminate, ordered according to some Gödel numbering.

Please clarify what the above means:  is it
a)  a list of [all algorithms for { computable numbers which are guaranteed to terminate } ], ordered according to some Gödel numbering.
or
b)  a list of [all algorithms for computable numbers] (which are guaranteed to terminate), ordered according to some Gödel numbering.
If (a) what do you mean by a "computable number that is guaranteed to terminate"?
If (b), the "which are guaranteed to terminate" is just a clarification since the computable number algorithm is indeed specified as terminating after producing the requested digit. (no problem)
Also, I'm taking it that you consider an "algorithm for a computable number" to be an algorithm (let's say a TM, to be definite) that takes a number n as input, and outputs the n'th digit of the computable number and then terminates.   Right?
I'll add further comments below when this is cleared up.

Apply the Cantor construction; that algorithm is also guaranteed to
terminate. Therefore it must have a Gödel number, and be located at a
finite place in the list -- call it Nₙ.
 So what happens when you ask the Cantor construction to compute digit Nₙ
of its number? It gets stuck in an endless loop. That means it is not
guaranteed to terminate. Therefore it cannot occur in the list.
 But if you take it out of the list, then it *will* terminate, because all
the rest of the elements in the list do so. Put it in, it doesn’t belong:
take it out, it does belong.
 So, by reductio ad absurdum, the assumption that the Cantor construction
for such a list even *exists* is false.
 

The Cantor diagonal argument works for every list of real numbers, and defines a number missing from the given list.  I explained that in my parent post.  Possibly you are just confused because the Cantor diagonal argument is not a "computation".  It's a definition of a particular number, which is subsequently shown to be missing from the given list.  The missing number in general might or might not be computable.
Regards,
Mike.