Path: ...!weretis.net!feeder9.news.weretis.net!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: Cantor Diagonal Proof
Date: Sun, 6 Apr 2025 17:39:30 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <356fe829b105738f556ce1f89999ae620dcd2071@i2pn2.org>
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> <vstme2$n9gi$2@dont-email.me>
 <HMScneI80ehcN2_6nZ2dnZfqn_SdnZ2d@brightview.co.uk>
 <vsuc78$1f8in$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 6 Apr 2025 21:46:12 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="3431431"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
In-Reply-To: <vsuc78$1f8in$1@dont-email.me>
Content-Language: en-US
X-Spam-Checker-Version: SpamAssassin 4.0.0
Bytes: 7917
Lines: 149

On 4/6/25 1:04 PM, Richard Heathfield wrote:
> On 06/04/2025 17:24, Mike Terry wrote:
>> On 06/04/2025 11:52, Richard Heathfield wrote:
>>> 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.
>>
>> Cantor made no reference to computability or computable numbers.
> 
> Nevertheless, that's precisely what Mr D'Oliveiro is talking about. From 
> the start of the thread:
> 
> "The Cantor diagonal construction is an algorithm for computing an 
> incomputable number. But if there is an algorithm for computing the 
> number, then it is by definition a computable number."
> 
> <snip>

First, Cantor's Diagonal Argument wasn't about construable numbers, but 
about numbers being countable.

It is a later analysis that shows that it is unconstructable.

And from what I see, the issue is that while each of the numbers in the 
list could be defined as constructable, in that a algorithm exists that 
given n, it will give at least n digits of that number, there doesn't 
need to be a master algorithm, that given k and n gives the first n 
digits of the kth number, that can be shown to cover the full set of 
constructable numbers (but perhaps an countable infinite subset of 
them). Without that master algorithm, the method of constructing the 
diagonal isn't actually an implementable algorithm.

We can't just iterate through all possible machines, because not all 
machines are halting, let alone meet the requirements for the 
construction machines.

Thus, we don't have an actual algorithm that makes the diagonal number 
constructable.

> 
>>>
>>> 2. Let D be the Cantor diagonal, eg via
>>>
>>> for(n = 0; n <= inf; n++)
>>> {
>>>    D[n] = (C[n][n] + 1) % 10;
>>> }
>>
>> You are writing the above as though it is some kind of step-by-step 
>> program to be executed.
> 
> It is an attempt to formalise what I believe to be what the OP considers 
> to be the relevant algorithm for arriving at the diagonal.
> 
>> That's a source of confusion amongst certain non-mathematicians, 
>> particularly those with a programming perspective on things.  (Not 
>> that you're confused - I'd just avoid such notation in case others are 
>> confused.)
> 
> It's just shorthand. I'm very willing to consider suggestions for 
> alternative ways to convey meaning so succinctly.
> 
>> The diagonal definition is just that: a definition, not a step by step 
>> sequence of anything.
> 
> Yes. We don't have to run alongside Achilles.
> 
>>> 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.
>>
>> Cantor was not concerned with computability.
> 
> Mr D'Oliveiro, however, is.
> 
>> His proof assumes we have the list as in (1), and constructs (defines) 
>> a new real number which is manifestly not in the list using the well 
>> known diagonal argument.
>>
>> There is no error with the construction of D, given the list. 
>> Depending on exact wording of the proof, it either shows that every 
>> list of reals misses at least one real number [the "anti-diagonal"], 
>> or that a contradiction is reached from the assumption that the 
>> original list was complete [the new anti-diagonal being a real number 
>> both in the list and not in the list] and so the assumption of 
>> completeness of the list was false.
> 
> Yes. Because of the way "computable" is defined, the same proof works 
> for computable numbers and suffices to debunk Mr D'Oliveiro.
> 
>>> 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.
>>>
>>
>> Hmmm, maybe you're talking about applying Cantor's argument to the 
>> list of computable numbers? Cantor never did that.
> 
> No, but Mr D'Oliveiro did.
> 
>> If we do this, we can certainly start with a list of computable 
>> numbers which is complete, since there are only countably many such 
>> numbers.  Then the anti-diagonal argument produces a new (non- 
>> computable) number that is not in the list.
> 
> Yes.
> 
>> It might seem that the number produced must be computable because the 
>> anti-diagonal "computes" it, but the anti-diagonal "computation" would 
>> only work given infinitely many digits of data out of the list.  (E.g. 
>> the whole list that you've called C[inf][inf] could be represented on 
>> a tape, or perhaps just the diagonal etc. but in any case the job 
>> can't be done with only a finite amount of data.
> 
> It's okay; we're playing with the whole set.
> 
>> Or perhaps we might think that a "computable list" of computable 
>> numbers could be constructed where a single TM can somehow generate 
>> all the C[inf][inf] on request (no extra data being input other than 
>> the row/col indices of the required entry). Then we could have one 
>> single TM that calculates all the anti-diagonal digits with no further 
>> data input from the expanded list since it can just calculate those 
>> digits as required.  That would present a contradiction since the new 
>> anti-diagonal number would then be computable!  But such a "computable 
>> list" is just wishful thinking and does not exist...
> 
> Actually, it does. I got it for Christmas in 1996. Last time I looked it 
> was somewhere in the loft.
>