Re: Flibble's Law

On 4/22/2025 5:35 PM, Keith Thompson wrote:

Mr Flibble <flibble@red-dwarf.jmc.corp> writes:

On Fri, 18 Apr 2025 17:13:23 -0400, Richard Damon wrote:

On 4/18/25 5:01 PM, Mr Flibble wrote:

If Busy Beavers are allowed an INFINITE tape in the context of the
Halting Problem then Simulating Halt Deciders are allowed INFINITE
resources.

>
Sure, they can use as much tape as they want, they just can't use
infinite time.

>
If they REQUIRE infinite tape then by implication they REQUIRE infinite
time.

 But they don't REQUIRE (does all-caps really help?) either infinite
tape or infinite time.  Unless I've misunderstood the concept, a Busy
Beaver by definition must terminate after a finite number of steps.
 We sometimes say "infinite tape" as a verbal shorthand for "as much
tape as is required".  Or we can say that infinite tape exists,
but we'll never use more than a finite amount of it.  The amount of
tape required is never actually infinite, but there is no specific
upper bound.
 (I sometimes wonder if we don't distinguish clearly enough between
"unbounded" and "infinite".)
 

That is an important nuance that many people miss.

There are actual (mathematically describable, not physically
implementable) Turing machines that consume infinite time and
infinite tape.  Busy Beavers do not.
 

Busy Beaver seems to quickly consume much more
memory than there are atoms in the universe.
--
Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer