Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!zaphod.mps.ohio-state.edu!samsung!transfer!lectroid!jjmhome!smds!sw
From: sw@smds.UUCP (Stephen E. Witham)
Newsgroups: comp.lang.misc
Subject: Re: Will this *thread* ever halt?
Summary: Different assumptions
Message-ID: <585@smds.UUCP>
Date: 24 Jun 91 14:29:15 GMT
References: <1991Jun18.172115.7185@clipper.ingr.com> <29254.Jun2219.22.4491@kramden.acf.nyu.edu>
Organization: SMDS Inc., Concord, MA
Lines: 19

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