Re: Cantor Diagonal Proof

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.

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.

I should have thought that was obvious.

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?