Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!wuarchive!uunet!mcsun!ukc!slxsys!ibmpcug!mantis!mathew From: mathew@mantis.co.uk (CNEWS MUST DIE!) Newsgroups: comp.lang.misc Subject: Re: Will this *thread* ever halt? Message-ID: Date: 22 May 91 10:59:58 GMT References: <30814@dime.cs.umass.edu> Organization: Mantis Consultants, Cambridge. UK. Lines: 142 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. > 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. OK. Give me an example of a C program which performs a major useful function, and does not use any features which would make halting analysis of that program dependent upon knowing exact details of the machine hardware. Just one. > 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. No. It is possible in theory for a C compiler to detect all paths that MIGHT lead to non-terminating loops. Anything more requires exact detailed knowledge about the hardware. And if you opt to flag all paths which MIGHT lead to non-terminating loops or system crashes, you'll end up with most of the program being flagged. > 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. Right. But the former two are properties of the machine environment the program will be running in, and can seriously affect whether the program halts. Look at all the programs which crashed when the system date on UNIX went past the size of an int. You can, in certain languages, make halting predictions; you can say "If this program is fed a file of finite size, it will terminate". C is not, in general, one of those languages. > 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. ...on this particular machine, running at this particular time, with this particular amount of processor stack, and so on. To get any useful GENERAL halting results would require massive restrictions on what you allowed in your "Halting ANSI C". Such severe restrictions that I doubt whether the language would be useful. > >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. Right. And whether a C program halts or not can be critically dependent upon the size of integers used in that particular implementation of C. So to perform your magic halting analysis, you need to know exactly how big integers are. And if your analysis is to be useful, this information needs to be directly or indirectly communicated to the programmer. Therefore the programmer needs to worry about exact implementation specifics. > >> A correctly written progra > >>will not depend on exactly how much memory is available, > > > >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. Really? Try running them in 1KB. 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. > >>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 [...] > >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. [...] > 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 said "an arbitrary C program". Not "an arbitrary C program which is not allowed to look at the system time". If your C code is not allowed to look at the system time, not allowed to use malloc (which effectively involves looking at available memory), not allowed to look at the file system (for temporary files) and so on, then yes, you probably can find out whether it will compute the correct value given any input. Now, how many useful programs do you know which satisfy those criteria? To look at it another way: Most C programs will end up with a list of inputs which includes system memory, clock, stack size, file system size, and so on. You will need to know the values of these inputs before you can determine whether the program will halt or not. This is not very useful. 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. If you still believe you can determine whether an arbitrary non-trivial ANSI C program will halt or not, and have that information generally applicable enough to be useful to the programmer, then go out there and do it and earn yourself millions. While you're at it, there are some guys in sci.skeptic who have a design for a perpetual motion machine which needs development. mathew