Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Richard Heathfield <rjh@cpax.org.uk>
Newsgroups: comp.theory
Subject: Re: Cantor Diagonal Proof
Date: Sun, 6 Apr 2025 11:52:50 +0100
Organization: Fix this later
Lines: 48
Message-ID: <vstme2$n9gi$2@dont-email.me>
References: <vsn1fu$1p67k$1@dont-email.me>
 <7EKdnTIUz9UkpXL6nZ2dnZfqn_ednZ2d@brightview.co.uk>
 <vsng73$27sdj$1@dont-email.me>
 <gGKdnZiYPJVC03L6nZ2dnZfqn_udnZ2d@brightview.co.uk>
 <vsnk2v$2fc5a$1@dont-email.me> <vsnmtg$2i4qp$3@dont-email.me>
 <vsno7m$2g4cd$3@dont-email.me> <vsnp0o$2ka6o$2@dont-email.me>
 <vsnpv4$2g4cd$6@dont-email.me> <vsntes$2osdn$1@dont-email.me>
 <vsntv3$2paf9$1@dont-email.me> <vso1a0$2sf7o$1@dont-email.me>
 <vso2ff$2tj1d$2@dont-email.me> <vso3rj$2vems$2@dont-email.me>
 <vso4gh$2vg3b$1@dont-email.me> <vsqmlb$1ktm5$6@dont-email.me>
 <vstl33$p9c2$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 06 Apr 2025 12:52:56 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="dbe7ec1ac8ffd7a60b5ada94cfd55d95";
	logging-data="763410"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/gU7q7OC7A54JObqVP3vliY6SXt+msXZA6nM/AnSsgYQ=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:2drGpP2m1qnDsGqFzp0Xw7ul7is=
In-Reply-To: <vstl33$p9c2$1@dont-email.me>
Content-Language: en-GB
Bytes: 3050

On 06/04/2025 11:29, Mikko wrote:
> On 2025-04-05 07:38:19 +0000, Lawrence D'Oliveiro said:
> 
>> On Fri, 4 Apr 2025 09:16:17 +0100, Richard Heathfield wrote:
>>
>>> Since all elements (except your two openers) begin with a 3, 
>>> none of
>>> them start 12, and so after just two iterations we have already
>>> constructed a number that's not in the infinite list.
>>
>> Remember that the hypothesis of the Cantor “proof” is that the 
>> list is
>> already supposed to contain every computable number. The fact 
>> that the
>> contruction succeeds for your list examples does not mean it 
>> will succeed
>> with mine.
> 
> How can Cantor's construction fail to succeed on a list?

As I understand it, his argument can be summarised as follows:

1. Let C[inf][inf] be a list of all the digits of all the 
computable numbers.

2. Let D be the Cantor diagonal, eg via

for(n = 0; n <= inf; n++)
{
   D[n] = (C[n][n] + 1) % 10;
}

3, Because we have computed D, it is a computable number, and 
therefore it must have an entry in C[, so the construction of D 
must somehow be in error.


The flaw, of course, is in overlooking that we required 
infinitely many steps to derive D. for(n = 0; n <= inf; 
n++){whatever} is not an algorithm, because by definition 
algorithms must have at most finitely many steps.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within