Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!dali.cs.montana.edu!caen!sdd.hp.com!spool.mu.edu!uunet!mcsun!ukc!slxsys!ibmpcug!mantis!mathew From: mathew@mantis.co.uk (CNEWS MUST DIE!) Newsgroups: comp.lang.misc Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions) Message-ID: Date: 17 May 91 18:32:28 GMT References: <30620@dime.cs.umass.edu> Organization: Mantis Consultants, Cambridge. UK. Lines: 120 yodaiken@chelm.cs.umass.edu (victor yodaiken) writes: > In article mathew@mantis.co.uk (CNEWS MUST DIE!) w > >yodaiken@chelm.cs.umass.edu (victor yodaiken) writes: > >> The kind of looping that makes Turing machines undecidable is quite > >> different from the kind of looping we get in real machines. On > >> a turing machine > >> while(true)i = i+1; > >> is a truly infinite loop, each iteration takes us to a new state. > >> But on a real computer, > >> while(true)i = i+1; > >> *will* repeat state (or crash the program). Here we have a *finite* loop. > > > >Only because either the machine's memory is finite, or because the specific > > Generally the case withthe machines I've seen. Yes, but do you want to have to be aware of exactly how much memory is available to your programs? > >> So it is, in > >> principle, quite possible to write an ANSI "C" compiler that would > >> detect non-terminating loops. The compiler would have to know someting > >> about the limits of adressable memory onthe machine, but, that does not > >> seem unreasonable. > > > >It would have to know EXACTLY how much memory was going to be available to > >the compiled program on execution, TO THE BYTE. > > Not true. Consider the following pseudo-code: i = 0 repeat allocate 1 byte of memory i++ until allocation fails if i is prime, while(1); end You can write such a program in ANSI C. In order to predict whether it will enter a non-terminating loop you have to know exactly how much memory is available to the program when it runs, to the byte. The result of running the program will be different according to the amount of memory the program is running in -- either virtual memory, or physical memory if the machine has no VM. The above example is contrived, but the same principles apply to any program which does dynamic memory management; you cannot in general guarantee that such programs will terminate. Look at buggy Lisp systems on small machines and their tendency to go into infinite-GC loops. You could maybe guarantee termination for the above program if your "allocate memory" routine aborted the program on failure, but making ANSI C's malloc() do that wouldn't be a very popular move. > >You would lose the abstraction of "int", "long" and so on; you would have to > >know EXACTLY how each data type was represented, and the results printed by > >the compiler would be critically dependent on that information. > > The programmer would not have to bother with these details, but the compiler > writer would have to know how data types were represented. But, it's hard > to imagine a compiler writer operating in ignorance of this information. OK. Suppose the programmer writes his code without worrying about type representation. He then compiles it on machine "A". The compiler says "Yes, it will terminate". Now, if the programmer wants to run his program on any other machine "B", he needs to know if "B"'s data type representation for the types he uses is the same as "A"'s in order to know whether his program will terminate. That's what I mean by "...would have to know EXACTLY how each data type was represented..." > >What's more, the compiler would probably have to run on a machine which was > >significantly larger than the target machine. > > If the algorithm was anything that I can come up with > right now (but, I would never have thought of quicksort either). I doubt that there will ever be an algorithm which will let a computer decide whether a program running on itself will halt. [ I expect there's a proof of that, which is probably much the same as the proof of the halting problem, but I'll leave it to someone else as it's Friday evening... ] > Or if the programming language was laxly designed. The restrictions you have to place on a language in order to enable guaranteed termination are such that the language is not useful for general programming. > Do you honestly believe that > a compiler that would warn you about exceeding memory limits or > looping indefinitely would not be of interest to most programmers? Yes. Firstly, the amount of memory I have free in this machine depends upon what I am running at the moment. Secondly, I want to know whether my programs will work on my friends' machines. Thirdly, I don't want to have to compile on a bigger machine than the one I'm going to run the program on. Finally, my compiler is slow enough already. The kind of analysis it would have to do for your hypothetical "terminating ANSI C" would make it mindbogglingly slow. I suspect that at least one of the above conditions holds for most programmers. mathew