Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!cs.utexas.edu!rutgers!psuvax1!hsdndev!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: Will this *thread* ever halt?
Message-ID: <12634.Jun2400.55.0891@kramden.acf.nyu.edu>
Date: 24 Jun 91 00:55:08 GMT
References: <ROCKWELL.91Jun22010647@socrates.umd.edu> <29254.Jun2219.22.4491@kramden.acf.nyu.edu> <1991Jun22.213750.18954@watserv1.waterloo.edu>
Organization: IR
Lines: 25

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