Path: ...!eternal-september.org!feeder3.eternal-september.org!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 --- PLO
Date: Sat, 5 Apr 2025 07:36:27 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 37
Message-ID: <vsqmhr$1ktm5$5@dont-email.me>
References: <vsn1fu$1p67k$1@dont-email.me> <vsqiha$1hl94$5@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 05 Apr 2025 09:36:28 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="9f11b097b26f2656761f9579e269a581";
	logging-data="1734341"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18TgpQg/TaotoXytbUoPBTf"
User-Agent: Pan/0.162 (Pokrosvk)
Cancel-Lock: sha1:TsKIcZE04G74QnjpYYwGwOJd+7I=
Bytes: 2781

On Sat, 5 Apr 2025 01:27:54 -0500, olcott wrote:

> I know nothing about computable numbers.

“A number which can be computed to any number of digits desired by a 
Turing machine.”
<https://mathworld.wolfram.com/ComputableNumber.html>

The concept is very simple: consider the number π. It is irrational, with 
no (known) patterns of repetitions among its digits, but it is computable: 
there are any number of algorithms known for computing it to any desired 
degree of accuracy. Computing the exact value of π would take infinite 
computation steps, but you can get as close as you like, without ever 
quite reaching it -- that is, the numerical computations “converge” to the 
right answer.

Since a computable number is computed by an algorithm, the possible number 
of computable numbers cannot be greater than the number of possible 
algorithms.

If an algorithm is expressed as a computer program, you can encode each 
symbol of the program as an integer, and end up with a huge integer that 
represents the program as whole -- this encoding is called “Gödel 
numbering”.

What this means is that the cardinality of the set of possible computer 
programs, while infinite, cannot be greater than the cardinality of the 
set of integers.

The cardinality of the set of integers (and therefore also the set of 
computer programs, and of the set of computable numbers) is conventionally 
written as ℵ₀. The cardinality of the set of reals is written as ℵ₁. Both 
are infinite, but ℵ₁ is supposed to be a larger infinity than ℵ₀ -- at 
least, that’s what the Cantor diagonal construction is supposed to prove.

In this thread I am trying to point out why the proof doesn’t work. For a 
start, in general, the diagonal construction never converges to an answer.