Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!wuarchive!udel!haven.umd.edu!socrates.umd.edu!socrates!rockwell From: rockwell@socrates.umd.edu (Raul Rockwell) Newsgroups: comp.lang.misc Subject: Re: Will this *thread* ever halt? Message-ID: Date: 23 May 91 00:41:26 GMT References: <3430@optima.cs.arizona.edu> <30863@dime.cs.umass.edu> Sender: rockwell@socrates.umd.edu (Raul Rockwell) Organization: Traveller Lines: 34 In-Reply-To: yodaiken@chelm.cs.umass.edu's message of 22 May 91 12: 08:38 GMT victor yodaiken: I argue that there is a deterministic *algorithm* with time/space bounded by the number of states of M, and that this algorithm can decide the halting problem for M. If we want, we can compute this algorithm on a FSM with sufficient state space (probably quite a bit larger than M). Well, yes. If you're dealing with an arbitrary machine, with 16k ram (8 bit bytes) you have to have a state space of over 10^(10^6) bits to store halting information (halts/doesn't) for every possible state. And this doubles every time you add a bit to the machine -- for a unix system with a gigabyte of disk space, your state space over 10^(8.26x10^10) bits (a number greater than 1 followed by over 82 billion zeros (decimal)). An the other hand, many algorithms can be easily shown to halt. (Any algorithm which is "primitive recursive" in the number-theoretic sense, which includes just about every computer programming technique except arbitrary loops and arbitrary recursion). So I can see why a person might want to say that the halting problem is solvable for a practical machine, but I wouldn't say that using state space is a useful solution. The solution I see is to limit yourself to a class of problems which are primitive recursive. From personal experience, I can say that you're still going to have to resort to state machine style techniques when you deal with i/o or secondary storage (secondary storage being defined as any storage not managed transparently by your target language). And I'm sure that any systems implementor can tell you horror stories about lurking race conditions and other potential bogosities in the os... Raul Rockwell