Path: ...!Xl.tags.giganews.com!local-2.nntp.ord.giganews.com!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 10 Apr 2025 16:11:38 +0000
Subject: Re: Cantor Diagonal Proof
Newsgroups: comp.theory
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>
 <356fe829b105738f556ce1f89999ae620dcd2071@i2pn2.org>
 <87y0waqknw.fsf@nosuchdomain.example.com>
 <QhycnWvtPMLZLmv6nZ2dnZfqnPqdnZ2d@brightview.co.uk>
 <vt75hu$1pl6i$8@dont-email.me>
From: Mike Terry <news.dead.person.stones@darjeeling.plus.com>
Date: Thu, 10 Apr 2025 17:11:43 +0100
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.18.2
MIME-Version: 1.0
In-Reply-To: <vt75hu$1pl6i$8@dont-email.me>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <kuOdnfXzB_UncGr6nZ2dnZfqn_WdnZ2d@brightview.co.uk>
Lines: 61
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-qaxBgehlsxSKFXRGK4QF+aYHCmnHktMghRENF7/bsNOyVTPBYiIGJ/FespUUMgkQIic2Gfjv4TOZbI0!et+gi3eL/cQsZPx1F0LcUDKze030daQhVStPDZBZIfvqWnn9sg2smLb4g64eUOtn1J/p3qvAWX6r!gCsY2gmAYmuRVNDcdkK80mUor7g=
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
Bytes: 4951

On 10/04/2025 02:06, Lawrence D'Oliveiro wrote:
> On Wed, 9 Apr 2025 18:49:54 +0100, Mike Terry wrote:
> 
>> The normal maths way of putting all this is that the set of computable
>> numbers is countable (can be "listed" / there exists a one-to-one
>> mapping from N to the computable numbers), and when the diagonal
>> argument is applied it results (as above) in a non-computable number
>> that's (obviously) not in the list.

If you would like me to comment on your suggestions below, we'll need to start by clarifying what 
you mean exactly.  That bit shouldn't take long, but given that your final conclusion below is 
obvious nonsense, you might consider it a waste of time...

> 
> Assume the list consists of algorithms for all computable numbers which
> are guaranteed to terminate, ordered according to some Gödel numbering.

Please clarify what the above means:  is it

a)  a list of [all algorithms for { computable numbers which are guaranteed to terminate } ], 
ordered according to some Gödel numbering.

or

b)  a list of [all algorithms for computable numbers] (which are guaranteed to terminate), ordered 
according to some Gödel numbering.

If (a) what do you mean by a "computable number that is guaranteed to terminate"?
If (b), the "which are guaranteed to terminate" is just a clarification since the computable number 
algorithm is indeed specified as terminating after producing the requested digit. (no problem)

Also, I'm taking it that you consider an "algorithm for a computable number" to be an algorithm 
(let's say a TM, to be definite) that takes a number n as input, and outputs the n'th digit of the 
computable number and then terminates.   Right?

I'll add further comments below when this is cleared up.

> Apply the Cantor construction; that algorithm is also guaranteed to
> terminate. Therefore it must have a Gödel number, and be located at a
> finite place in the list -- call it Nₙ.
> 
> So what happens when you ask the Cantor construction to compute digit Nₙ
> of its number? It gets stuck in an endless loop. That means it is not
> guaranteed to terminate. Therefore it cannot occur in the list.
> 
> But if you take it out of the list, then it *will* terminate, because all
> the rest of the elements in the list do so. Put it in, it doesn’t belong:
> take it out, it does belong.
> 
> So, by reductio ad absurdum, the assumption that the Cantor construction
> for such a list even *exists* is false.
> 
The Cantor diagonal argument works for every list of real numbers, and defines a number missing from 
the given list.  I explained that in my parent post.  Possibly you are just confused because the 
Cantor diagonal argument is not a "computation".  It's a definition of a particular number, which is 
subsequently shown to be missing from the given list.  The missing number in general might or might 
not be computable.

Regards,
Mike.