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: Sat, 5 Apr 2025 09:07:22 +0100
Organization: Fix this later
Lines: 51
Message-ID: <vsqobq$1mglg$3@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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 05 Apr 2025 10:07:24 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="9ba5473c49a0346d8825952a0365662d";
	logging-data="1786544"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/8EpPROVb0cE5w3Ucr4nYOFInklrDOBN1vaNB8upPG7Q=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:/yjRqXv3oFP7pnpIOuR6dIm/yzg=
Content-Language: en-GB
In-Reply-To: <vsqmlb$1ktm5$6@dont-email.me>
Bytes: 3358

On 05/04/2025 08:38, Lawrence D'Oliveiro wrote:
> 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.

On that we can agree. The proof works for any list.

> The fact that the
> contruction succeeds for your list examples does not mean it will succeed
> with mine. Remember, the “proof” depends on it succeeding in the general
> case, with every possible list.

Indeed it does. Let's use some syntax.

Let the list be digit_t C[inf][inf] (I'm using a gcc extension 
that allows infinitely sized arrays). Let the diagonal be D[inf]

Cantor's construction can be expressed as:

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

Cantor correctly reasons that, at the point where Achilles 
catches the tortoise, the number stored in D does not appear in 
any of C's rows (or columns, come to that).

Your argument appears to be that, since C contains all computable 
numbers, and since we just computed D, D must already be in C.

But to be computable, numbers must be computed in a finite number 
of steps. To compute D requires /infinite/ steps. We can reason 
about D without taking forever over it, but we can't /compute/ it 
this side of eternity.

You wrote: "But if there is an algorithm for computing the number"

But there isn't. Diamonds are forever, but algorithms must terminate.

-- 
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