🚀 go-pugleaf

In article <TcT422w164w@mantis.co.uk> mathew@mantis.co.uk (CNEWS MUST DIE!) writes:
>yodaiken@chelm.cs.umass.edu (victor yodaiken) writes:
>> In article <eqJZ22w164w@mantis.co.uk> 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 ....