🚀 go-pugleaf

In article <eqJZ22w164w@mantis.co.uk> 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?