Path: ...!eternal-september.org!feeder3.eternal-september.org!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: Cantor Diagonal Proof
Date: Sun, 13 Apr 2025 19:39:33 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <4de710ba8480d3b428a39d6cb5e571da24c67033@i2pn2.org>
References: <vsn1fu$1p67k$1@dont-email.me> <vsr1ae$1pr17$2@dont-email.me>
 <vst4nm$8daf$2@dont-email.me> <vst8ci$aeqh$3@dont-email.me>
 <vsutjt$21mp2$2@dont-email.me> <vsuvp1$227l5$1@dont-email.me>
 <vsvv3h$36pju$2@dont-email.me> <vt01u5$38f07$1@dont-email.me>
 <875xjfd5rs.fsf@nosuchdomain.example.com> <vt1jpa$n43m$4@dont-email.me>
 <87tt6zblzl.fsf@nosuchdomain.example.com>
 <0920ac6e196c1cebeff36d8b9431ee12a7b3d527@i2pn2.org>
 <vt74k1$1pl6i$5@dont-email.me>
 <74db303c1d07ba0fdf70f1b20f5f7d6e04667665@i2pn2.org>
 <vt9nr3$5t7s$5@dont-email.me>
 <4f2f706fdbd8bb237b4bfbc750f65482db6e96c7@i2pn2.org>
 <vtag8u$vqm0$3@dont-email.me>
 <c7320364d5ad63cd30018fa0082e8dcc60ad2534@i2pn2.org>
 <vtc4ao$2mlfb$4@dont-email.me>
 <84c84545ad9509384f5378553217346b12512a97@i2pn2.org>
 <vtha1c$3oh15$2@dont-email.me> <87h62rg1rx.fsf@nosuchdomain.example.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 14 Apr 2025 00:02:03 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="241454"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
Content-Language: en-US
In-Reply-To: <87h62rg1rx.fsf@nosuchdomain.example.com>
X-Spam-Checker-Version: SpamAssassin 4.0.0
Bytes: 2890
Lines: 25

On 4/13/25 6:00 PM, Keith Thompson wrote:
> Lawrence D'Oliveiro <ldo@nz.invalid> writes:
>> On Fri, 11 Apr 2025 21:41:48 -0400, Richard Damon wrote:
>>> Yes, but since you need the algorithms to compute ALL the numbers in
>>> your code, you can't put them all in.
>>
>> But the Cantor construction relies on constructing precisely such a list.
>> If you can’t put together such a list, then you can’t perform the Cantor
>> construction.
> 
> The Cantor construction *assumes* the existence of such a list,
> demonstrates that that assumption leads to a contradiction, and
> concludes that no such list can exist.
> 

Cantor shows that no list of REAL numbers can be created.

But there is also the later reuse of the arguement for the domain of 
Computable Numbers, and there, the list CAN be made (but not computed). 
One method can simply use the axiom of choice and sorting of 
representations.

What this shows is that since we KNOW the computable numbers must be 
countable, that the diagonal must not be computable, and thus there is 
no "master algorithm" that can compute and arbitrary digit of an 
arbitrary number.