Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Julio Di Egidio <julio@diegidio.name>
Newsgroups: comp.theory
Subject: Re: Cantor Diagonal Proof
Date: Fri, 4 Apr 2025 13:47:29 +0200
Organization: A noiseless patient Spider
Lines: 20
Message-ID: <vsogsi$38bb3$1@dont-email.me>
References: <vsn1fu$1p67k$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 04 Apr 2025 13:47:30 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="e0fe30d62e6444ee8a40554b8abe7083";
	logging-data="3419491"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18nv7ij6LqCn30SYh2bC6d4YaqKVFSTyCo="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:gBf3pFO50SBTCyZAFQ9WJe93jTo=
In-Reply-To: <vsn1fu$1p67k$1@dont-email.me>
Content-Language: en-GB, it
Bytes: 1792

On 04/04/2025 00:18, Lawrence D'Oliveiro wrote:

> The Cantor diagonal construction is an algorithm for computing an
> incomputable number.

To be more precise, it is an argument, not an algorithm, although it
is a fact that "diagonalisation" as a method has become ubiquitous.
BTW, the argument has indeed been proved constructively: or so they
say, I find that debatable as it needs *extensionality*.

> But if there is an algorithm for computing the number, then it is by
> definition a computable number.

The anti-diagonal is *as computable as the list is*: and the argument
in fact proves there can be no such list, computable or otherwise...
(no complete list of all such *sequences*: the connection to the real
*numbers* is a further step and problem).

-Julio