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: Halting Problem Solved! Film at 11! (Was Re: definitions) Message-ID: <30620@dime.cs.umass.edu> Date: 16 May 91 15:19:45 GMT References: <30514@dime.cs.umass.edu> Sender: news@dime.cs.umass.edu Organization: University of Massachusetts, Amherst Lines: 71 In article mathew@mantis.co.uk (CNEWS MUST DIE!) writes: >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. >> Similarly, bounded recursion, even with implicit bounds, is all we have >> on real computers -- eventually stacks will overflow. > >True. But all these bounds may be intractably large given virtual memory This bears repeating: intractably large != infinite. What is intractably large today may be easy tomorrow if someone thinks hard enough. What is infinite today, will be infinite tomorrow. The state space of the 8 queens problem was intracatably large to Gauss, yet it's no problem for anyone with access to a PC. The traveling salesman problem is probably inherently exponential, but smart algorithms make it reasonable tractable. "Intractable" means "nobody has thought of a good algorithm yet, and perhaps there is no such algorithm". "Infinite" means, "there is no good algorithm". >> 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. It would have to know the limits of adressable memory on the machine. Thus, it would sometimes err by detecting an "infinite loop" in a program that will really crash. Or, under many operating systems, the compiler would be able to know the maximum size of process data space without much effort. >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. >What's more, the compiler would probably have to run on a machine which was >significantly larger than the target machine. You could write your program If the algorithm was anything that I can come up with right now (but, I would never have thought of quicksort either). Or if the programming language was laxly designed. >and have it compile and have the compiler say "yes, this will terminate"; >you could then try running the program on a machine with slightly more disk >space, or a different version of the OS, and suddenly it would fail to >terminate. Similarly, some programs will run correctly only if certain o.s. or machine dependent conditions are met. 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?