Re: Cantor Diagonal Proof

On 11/04/2025 01:36, Lawrence D'Oliveiro wrote:

On Thu, 10 Apr 2025 17:11:43 +0100, Mike Terry wrote:
 

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

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"?

 I didn’t come up with that phrase, you did.

ok, so you intend (b) above.
So far we have a lexically ordered list of algorithms for computable numbers.  And obviously an associated list of computable numbers (which is what the Cantor diagonalisation argument applies to).  Both these lists are countable, so they are complete.
The list of computable numbers (to which Cantor's diagonalisation argument applies) will contain duplicates since each computable number has many algorithms that correspond to it.  But that's not a problem - it is still diagonalisable, and the diagonalisation argument produces a missing real number not in the list.  (Obviously that missing real cannot be computable...)

 

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?

ok, I'll take that as a yes.

>
I'll add further comments below when this is cleared up.

 I should have thought that was obvious.

I've restored the part of your earlier text so that I can comment further...
------ restored text ------
 >>> Apply the Cantor construction; that algorithm is also guaranteed to
 >>> terminate.
The Cantor construction is not an algorithm.  It assumes as given a list of real numbers, and defines a particular real number which is subsequently shown to be missing from that origial list.
Since it is not an algorithm, termination is simply not a term that applies to it.
So... it seems you are thinking of something else, different to what Cantor was talking about.
That's ok - If you have an "algorithm" in mind at this point in your argument, can you explain what you are thinking?  What are the concrete steps of this algorithm which you say is guaranteed to terminate?  What does it operate on exactly, and what does it produce?
It sounds from what you say below that you are thinking of some algorithm associated with a computable number ???  [So your algorithm would have input data: n, and produce the n'th digit of some number...]
 >>> 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.
------ end of restored text ------

 

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.

 Are you saying the Cantor construction is not an algorithm?
 

Of course, lots of people have explained that already, including me.  If you have an algorithm in mind here, that's ok - just continue clarifying as requested above, and we'll get there in the end.
Regards,
Mike.