Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!samsung!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: <30814@dime.cs.umass.edu> Date: 21 May 91 15:16:45 GMT References: Sender: news@dime.cs.umass.edu Organization: University of Massachusetts, Amherst Lines: 84 In article mathew@mantis.co.uk (CNEWS MUST DIE!) writes: >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. > The way you cast the problem evades the TM/FSM question. Yes. Programs that depend on particularities of machine configuration do depend on particularities of machine configuration. If we write a program P that requests specific machine configuration information, and then choses a path based on that data, then the operation of the program will not be the same on all machines. But, this is essentially the same situation as i/o dependencies. I argue that it is possible, in theory, for a C compiler to detect all paths that lead to non-terminating loops and to flag these paths. It is not possible for a "C" compiler to determine, in advance, the result of checking the current time, asking how much memory is available, or reading the next character typed on a terminal. These questions are not undecidable in the technical sense, they are simply undetermined. >How many non-trivial C programs don't use dynamic memory allocation? Sure, >you can restrict yourself to fixed-size data structures, but that leads to >even WORSE problems when you try to handle I/O. If we give X.c to the hypothical smart compiler and it tells us that X.c contains a path that exceeds the process memory limits on this machine, or that X.c contains a path that will cause it to enter a non-terminating loop if "alloc" fails, then the compiler has solved the halting problem for this code. >>Again, you raise a valid issue, but I'm not clear how it applies to the >>point at hand. If I write a program that can run correctly given a "C" >>compiler that uses 32bits to represent integers, but which will loop >>given an 8 bit "C" compiler, the compilers can flag the error, without >>requiring the programmer to worry about exact representation. > >Eh? The programmer wants his program to work. If it works for 32 bit ints >but not for 16 bit ints, then he has to worry about exact representation. >Having the compiler say "your program doesn't work because this machine has >16 bit ints" does not mean that the programmer doesn't have to worry about >it. You've lost me here. The correctness of "C" programs can depend on how the compiler implements "ints". This is a feature of the "C" language, not an artificial constraint that I'm inventing. Programmers cannot treat "C" as if it were more high level than it is, and expect to get away with it. >> A correctly written program >>will not depend on exactly how much memory is available, and if the compiler >>flags such a dependency, then it has found what is most likely an error. > >In that case, there are no correctly-written programs which perform >non-trivial tasks. > Can you give me an example of such a program. The "C" compiler, lisp interpreter, emacs editor, news-reader, operating system, computer algebra programs and and theorem provers we have around here seem to be able to tolerate wide variations in available memory. > >>If I had a "C" compiler that would run on, say, an IBM PC with at least >>6 meg of memory and a large disk, which would tell me within a few days >>whether or not an arbitrary "C" program would fail given at most >>X bytes of memory (X < 3 meg), then >>I believe that at least a few people would be interested >>in using it. > >Indeed. But you can't do it. Even knowing the exact value of X doesn't help; >you have to know other things such as the value of the system clock. >(Consider "if seconds = 32 then while (1)"). > 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.