🚀 go-pugleaf

In article <gZy9221w164w@mantis.co.uk> mathew@mantis.co.uk (CNEWS MUST DIE!) writes:
>In general, though, determining whether a program will halt on a real
>computer by analysing it as a FSM requires knowledge about exactly how much
>memory is available.
>

The way you cast the problem evades the TM/FSM question.  Yes. Programs
that depend on particularities of machine configuration do depend on
particularities of machine configuration. If we write a program P that
requests specific machine configuration information, and then choses
a path based on that data, then the operation of the program will not
be the same on all machines. But, this is essentially the same situation
as i/o dependencies. I argue that it is possible, in theory, for a C
compiler to detect all paths that lead to non-terminating loops and to
flag these paths. It is not possible for a "C" compiler to determine,
in advance, the result of checking the current time, asking how much
memory is available, or reading the next character typed on a terminal.
These questions are not undecidable in the technical sense, they are
simply undetermined.

>How many non-trivial C programs don't use dynamic memory allocation?  Sure,
>you can restrict yourself to fixed-size data structures, but that leads to
>even WORSE problems when you try to handle I/O.

If we give X.c to the hypothical smart compiler and it tells us that
X.c contains a path that exceeds the process memory limits on this
machine, or that X.c contains a path that will cause it to enter a
non-terminating loop if "alloc" fails, then the compiler has solved
the halting problem for this code.

>>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.
>
>Eh?  The programmer wants his program to work. If it works for 32 bit ints
>but not for 16 bit ints, then he has to worry about exact representation.
>Having the compiler say "your program doesn't work because this machine has
>16 bit ints" does not mean that the programmer doesn't have to worry about
>it.

You've lost me here. The correctness of "C" programs can depend on how
the compiler implements "ints". This is a feature of the "C" language, not
an artificial constraint that I'm inventing. Programmers cannot treat
"C" as if it were more high level than it is, and expect to get away with
it. 


>>                                                 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.
>
>In that case, there are no correctly-written programs which perform
>non-trivial tasks.
>

Can you give me an example of such a program. The "C" compiler, lisp
interpreter, emacs editor, news-reader, operating system, computer
algebra programs and and theorem provers we have around here seem to 
be able to tolerate wide variations in available memory.

>
>>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.
>
>Indeed. But you can't do it. Even knowing the exact value of X doesn't help;
>you have to know other things such as the value of the system clock.
>(Consider "if seconds = 32 then while (1)").
>

Again, you mistake the nature of the problem. If I claim that P
implements the function f: D -> D', then I am claiming that for any
x in the appropriate domain running P on input x will result in 
the value f(x). If the compiler can tell me that there is an x inthe
domain that causes P to enter a non-terminating loop, then the compiler
has detected a bug in my program. You are arguing that the compiler will
not be able to predict x. So what? Generally, we want to know whether the
program will compute the correct value given any input, and we include
such things as system time among the inputs.