🚀 go-pugleaf

In article <29254.Jun2219.22.4491@kramden.acf.nyu.edu>, brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
> In article <ROCKWELL.91Jun22010647@socrates.umd.edu> rockwell@socrates.umd.edu (Raul Rockwell) writes:
> > Detecting loops on a machine with n states requires O(2^n) states in
> > the analyzer.
> 
> This is the equivalent in computer ``science'' of an old wives' tale.

There is a difference of assumptions here that has been going on through
this whole thread.

If you know all the inputs to your program, then it's equivalent to an FSM
starting in a certain state, and you can find out whether it halts with
two copies of the FSM--twice the memory, O(n^2) states.

If you don't know all the inputs in advance, then you're trying to
find out whether a whole class of FSMs halt.  For n bits of input, that's
2^n different problems.

--Steve