Re: Flibble's Law

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 */