Re: Cantor Diagonal Proof

On Sat, 5 Apr 2025 11:05:51 +0100, Andy Walker wrote:

On 05/04/2025 03:20, Lawrence D'Oliveiro wrote:

>
On Sat, 5 Apr 2025 00:09:13 +0100, Andy Walker wrote:

>
-- The construction of a computable number that differs from every
    number in the list shows that there is no way to construct a list
    of all computable numbers ...

>
... which in turn must mean that there is no way to construct a list of
all integers, which is clearly nonsense.

 
No it doesn't.

Think about what it means to construct a list of the computable numbers.
You can’t, of course, physically write out a number of infinite digits. So
what you can do instead is write (or at least try to write) a list of the
computer programs, in the form of callable functions, for calculating each
computable number, ordered according to some Gödel numbering. Each
function takes a single positive integer parameter N, and is supposed to
return the Nth digit of its computable number.

So the complete Cantor construction becomes
  * call the first function in the list with argument 1, pick a digit
different from the result it returns, and make that the first digit of my
result
  * call the second function in the list with argument 2, pick a digit
different from the result it returns, and make that the second digit of my
result
  ...

In short, it, too, can be expressed as a function of a single positive
integer parameter N, which calls the Nth function in the list with
argument N, picks some digit different from the result it returns, and
makes that the Nth digit of its result.

And this, being an algorithm in its own right, will have its own position
in our Gödel numbering scheme. Which means it will occur at some position
in the list of computable number functions. Call its position Nₙ.

So what does this Cantor function do when asked to compute digit Nₙ of its
result?

Of course, it will call the function at position Nₙ, which happens to
be ... itself. Which in turn will call the function at position Nₙ ...
which is itself. And so on and so on.

So in short, it gets stuck in an endless loop. So the digit at position Nₙ
of the Cantor construction is *undefined*.

So you see now, why the Cantor construction for computable numbers cannot
complete. It cannot be expressed as an algorithm that terminates after a
finite number of steps for any valid input. So there can be no proof that
the computable numbers *cannot* be placed in 1:1 correspondence with the
integers. QED!