Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Keith Thompson <Keith.S.Thompson+u@gmail.com>
Newsgroups: comp.theory
Subject: Re: Flibble's Law
Date: Tue, 22 Apr 2025 20:23:33 -0700
Organization: None to speak of
Lines: 42
Message-ID: <877c3by30q.fsf@nosuchdomain.example.com>
References: <HjxMP.837300$7Fq7.451049@fx13.ams4>
	<19955e68400bc2ad935f413f012fe04011f7cf75@i2pn2.org>
	<V4zMP.1406251$NN2a.623234@fx15.ams4>
	<7c47bbe68c1cf317ddb2a0418564127c1471e11b@i2pn2.org>
	<X0MNP.1451996$cgs7.1194221@fx14.ams4>
	<87jz7bygci.fsf@nosuchdomain.example.com>
	<vu9684$1h90v$2@dont-email.me>
	<8b378dd6e80850b959dcebd414c8c78e82752266@i2pn2.org>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Wed, 23 Apr 2025 05:23:36 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="559a91cae6b172c7f978eee8629ad54d";
	logging-data="2198073"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+XBDL5WjZHa3umlPLS10t0"
User-Agent: Gnus/5.13 (Gnus v5.13)
Cancel-Lock: sha1:8pTKUFnjBuV3VWIKrzlAT8PqgLE=
	sha1:9lGUpjyZOkpRoMfjre/mr/stG8g=

Richard Damon <richard@damon-family.org> writes:
[...]
> Yes, there is a nuance, but there ARE some processes that aren't just
> unbounded by go infinite. Unbounded can only reach countable infinity,
> but not uncountable infinity. Thus a process that was performing the
> super-task of writing out all the real numbers between 0 and 1 would
> use TRULY infinite tape (needing at least Aleph-1 cells) and infinite
> time to complete.

Hmm.  It seems to me that that would be beyond the scope of any
Turing machine.

A trivial Turing machine could write out an unending sequence of
1s to its tape, never halting.  Such a machine would need a truly
infinite tape (Aleph-0 cells) if you let it run for an infinite
time.  I suppose you could loosely say that it "finishes" its task
of writing infinite 1s after an infinite time.  Another TM could
repeatedly write 1s to the same location without moving the tape;
such a machine could be left running for an infinite type but would
only consume finite tape.

I suggest that something that can potentially execute Aleph-1 steps
or consume Aleph-1 tape cells is not a TM.

> In the same way, an unbounded process, could be thought of, as
> "finishing" after a countable infinite number of steps, while another
> process might just never stop as in a countable infinite number of
> steps it never reaches its end (because it takes an uncountable
> infinite number of steps).

I'd say that a TM that takes a countably infinite number of steps
just never completes (though we can discuss the *limit* of its
output), while a machine that takes an uncountably infinite number
of steps isn't a TM.

Actual experts, please jump in and tell me where I'm wrong.

[...]

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */