🚀 go-pugleaf

In article <1991Jun22.213750.18954@watserv1.waterloo.edu> mhcoffin@tolstoy.waterloo.edu (Michael Coffin) writes:
> The technique you
> describe is well known by most computer scientists,

Some, at least. So how come there are so many published statements that
to detect loops in an n-bit computer requires 2^n bits? I first saw this
statement in a DDJ article---surely DDJ's editors don't all suffer the
same delusion!

> It doesn't make a "practical solution" to
> the halting problem because can take a long, long time to run.

But in *practice* most loops cycle through a very small set of states.
This is true of nearly all the infinite loops I've seen, both in my code
and in code I've had to maintain.

> Can a solution to the halting problem be said to be "practical" if it
> takes millenia to terminate when applied to a simple program that uses
> less than 12 bytes of state?

There will always exist programs of length n that run for 2^2^{kn}
steps before stopping. In *practice* very few programs exhibit such
behavior.

---Dan