Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Lawrence D'Oliveiro <ldo@nz.invalid>
Newsgroups: comp.theory
Subject: Re: Cantor Diagonal Proof
Date: Thu, 10 Apr 2025 01:06:06 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 24
Message-ID: <vt75hu$1pl6i$8@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> <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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 10 Apr 2025 03:06:06 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="2db6b81a4d73fd9d5766f02e33a0093e";
	logging-data="1889490"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/fqyvd+snzvFlYZAlA2s35"
User-Agent: Pan/0.162 (Pokrosvk)
Cancel-Lock: sha1:jiTN4Qy7JEscCpsXU8+8XWTmAJk=

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.

Assume the list consists of algorithms for all computable numbers which
are guaranteed to terminate, ordered according to some Gödel numbering.
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.