Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Lawrence D'Oliveiro <ldo@nz.invalid>
Newsgroups: comp.theory
Subject: Re: Cantor Diagonal Proof
Date: Sat, 5 Apr 2025 20:39:50 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 56
Message-ID: <vss4em$35ali$1@dont-email.me>
References: <vsn1fu$1p67k$1@dont-email.me> <vsogsi$38bb3$1@dont-email.me>
	<vspoqp$3nc7g$1@dont-email.me> <vsq41a$10hfp$4@dont-email.me>
	<vsqv9v$1pr16$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 05 Apr 2025 22:39:51 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="9f11b097b26f2656761f9579e269a581";
	logging-data="3320498"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+IcGggsswAom4DuZQ5MlrT"
User-Agent: Pan/0.162 (Pokrosvk)
Cancel-Lock: sha1:tJihbXNZtAn+Qzx3Hku3tiAhU7Q=
Bytes: 3620

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!