Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!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: Halting Problem Solved! Film at 11! (Was Re: definitions) Message-ID: <30741@dime.cs.umass.edu> Date: 19 May 91 13:10:45 GMT References: <30620@dime.cs.umass.edu> Sender: news@dime.cs.umass.edu Organization: University of Massachusetts, Amherst Lines: 155 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!) 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? Not always. But, for the compiler to warn me that "while(1)i =i+1" will either crash or cycle state forever does not require me to know this information. And if the compiler were compiling a program for a Turing machine the program would do neither. >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. If your point is that one can write ANSI "C" programs that are machine specific, sure. And if your point is that one can write ANSI "C" programs that will depend on I/O or operating system behavior, I also agree. I do not claim that one can write a "C" compiler that will predict how an unspecified o.s. or a input channel will behave (except that the behavior will fall in some range. e.g., when we read a "byte", we get one of 256 values). The program "read byte into x, if x=='a' while(1); else exit" is inherently unpredictable unless we have a model of the i/o channel. The compiler cannot predict such paths, but it can warn us when our programs contain i/o dependent paths that can lead to indefinite cycles. This is the case in your example. Note, the turing theorem has nothing to do with predicting behavior of your code. If we had an oracle for Turing machines, the oracle would still not be able to predict the behavior of "alloc" . >> 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..." 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. The program "int i = 1; while(i++ != 0)print(i)" will behave differently under the different compilers. This is an inescapable fact. We provide abstractions in our programmng languages, but these are conveniences which do not negate the facts that real machines do not have "integers" and "real numbers", but only have limited representations of these mathematical abstractions. Even if the compiler implements "i" with a variable format (e.g. bignums), the programmer will want to know if the program may exceed thelimits of machine representation. 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. >> >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. > There won't be. The key phrase here is "significantly larger". >> 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. Demonstrate this? Any demonstraton would seem to require unusually precise information about the limits of ingenuity. > >> 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. > See above. >Secondly, I want to know whether my programs will work on my friends' >machines. > Try compiling on those machines, or compile with a "portability" flag. >Thirdly, I don't want to have to compile on a bigger machine than the one I'm >going to run the program on. > For many applications, this is not a problem, either because the target machine cannot support a compiler (e.g., embedded systems), because correctness of the application is of great interest (e.g., if you are releasing a program that you hope will run on all Mac's with at least 1 meg of memory), or because the o.s. limits each program to an adressable memory space that is less than the available machine space (e.g. most operating systems on memory mapped machines). 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. >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. > We started with a question about Turing computability and end up with arguments about how slow "C" compilers are these days. Why I remember running the "C" compiler on a PDP-11/45 with 128K and in those days we didn't need all these fancy optimizers, portability testers, and other stuff, we were happy just to get away from VM and PL/1. You kids these days ....