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
Date: Fri, 11 Apr 2025 22:15:53 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 30
Message-ID: <vtc4ao$2mlfb$4@dont-email.me>
References: <vsn1fu$1p67k$1@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> <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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 12 Apr 2025 00:15:53 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="2e5924fe3d9905cd5f265cdbfb6deffb";
	logging-data="2840043"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19dVN+j4GLD603kG6GxTHKr"
User-Agent: Pan/0.162 (Pokrosvk)
Cancel-Lock: sha1:PROZynmSVCMyku0gFNVB81qoVNI=
Bytes: 3051

On Fri, 11 Apr 2025 09:15:38 -0400, Richard Damon wrote:

> On 4/11/25 3:27 AM, Lawrence D'Oliveiro wrote:
>>
>> On Thu, 10 Apr 2025 21:29:51 -0400, Richard Damon wrote:
>> 
>>> On 4/10/25 8:30 PM, Lawrence D'Oliveiro wrote:
>>>
>>>> On Wed, 9 Apr 2025 22:00:15 -0400, Richard Damon wrote:
>>>>
>>>>> The problem with the "Cantor Construction" is that one of the steps,
>>>>> "Compute to the Nth digit of the Nth number" isn't computable with a
>>>>> finite algorithm.
>>>>
>>>> But N is always finite, therefore the construction is always finite.
>>>
>>> N my be finite, but is unbounded, and thus the construction is
>>> unbounded in size, and thus not finite.
>> 
>> Why is N allowed to be finite but unbounded, but not the construction?
> 
> Because N is a variable, but the construction is supposed to be a
> constant.

Do you know how loops work in algorithms? A finite amount of code can be 
executed an unbounded number of times. Without this capability, we would 
have no “halting problem”. The construction can be conveyed with a finite 
amount of information, which makes it finite.

(See also “primitive recursive”.)