Re: Flibble's Law

On 4/22/25 6:46 PM, olcott wrote:

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.

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.
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).

 

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.
 

Some do, but mostly it is the programs pretending to be Busy Beavers that actually never halt, and thus are not actually Busy Beavers.