Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!bu.edu!transfer!lectroid!jjmhome!crackers!m2c!risky.ecs.umass.edu!dime!chelm.cs.umass.edu!yodaiken From: yodaiken@chelm.cs.umass.edu (victor yodaiken) Newsgroups: comp.lang.misc Subject: Re: Will this *thread* ever halt? Message-ID: <31051@dime.cs.umass.edu> Date: 24 May 91 14:41:37 GMT References: <30814@dime.cs.umass.edu> Sender: news@dime.cs.umass.edu Organization: University of Massachusetts, Amherst Lines: 69 In article mathew@mantis.co.uk (CNEWS MUST DIE!) writes: >yodaiken@chelm.cs.umass.edu (victor yodaiken) writes: >> In article mathew@mantis.co.uk (CNEWS MUST DIE!) >> >In general, though, determining whether a program will halt on a real >> >computer by analysing it as a FSM requires knowledge about exactly how much >> >memory is available. I'm really mystified by this discussion. Part ofthe problem may arise from the odd idea of "exact" that you seem to hold. You write: >There will be some lower memory threshold x beneath which the programs will >not run. If you have x-1 bytes of memory, the programs will not run. It is >therefore important that the exact amount of memory you have is greater than >x. This is a condition on exactly how much memory must be available. Equality >isn't the only condition which requires you to know exact amounts. > Forgive me if I mistake your meaning, but this seems like complete nonsense. The expression x> 10 does not constrain x to an "exact amount". If emacs requires at least 4 meg of memory in order to run correctly, then knowing that x>4meg is certainly good enough. A second problem arises from your misuse of the term "halting problem". The halting problem involves deterministic machines. It does not involve predicting the time of day which you will chose to run a program or the next word which I will type into a keyboard. A computer program can be considered to be a deterministic machine computing a function on its input. You want to say that program behavior is not deterministic, because the input is not deterministic. Generally, however, we are less interested in predicting system input than in making sure that the program can cope correctly with *every* possible input. When I say that we can, in theory, decide whether or not a "C" program contains an non-terminating loop, I do not mean to suggest that we can decide in advance whether or not it will ever enter that loop. The program "read c; if c='\n' while(1); exit" contains a reachable non-terminating loop. You may be content to run this program without ever hitting a cariage return. I'm not, however, interested in predicting your behavior. I wrote: >> Again, you mistake the nature of the problem. If I claim that P >> implements the function f: D -> D', then I am claiming that for any >> x in the appropriate domain running P on input x will result in >> the value f(x). If the compiler can tell me that there is an x inthe >> domain that causes P to enter a non-terminating loop, then the compiler >> has detected a bug in my program. You are arguing that the compiler will >> not be able to predict x. So what? Generally, we want to know whether the >> program will compute the correct value given any input, and we include >> such things as system time among the inputs. > You reply: >You said "an arbitrary C program". Not "an arbitrary C program which is not >allowed to look at the system time". > Here, I'm considering the program as a function with input varying over its domain. In this case, consider the domain to be the set of possible time values. We don't want to attempt to predict which elements of this domain will be encountered: i.e., we don't want to try to predict the time of day when the program will be run. We just want to make sure that the program behaves "correctly" for any time value. >I'm about ready to give up arguing with you. You seem to be just as clueless >as when you started, and I really have better things to do than argue about >whether you can solve the halting problem for general ANSI C programs. Go to 'em.