Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!slxsys!ibmpcug!mantis!mathew
From: mathew@mantis.co.uk (CNEWS MUST DIE!)
Newsgroups: comp.lang.misc
Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions)
Message-ID: <eqJZ22w164w@mantis.co.uk>
Date: 15 May 91 11:14:13 GMT
References: <30514@dime.cs.umass.edu>
Organization: Mantis Consultants, Cambridge. UK.
Lines: 48

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
implementation of the language being used imposes some arbitrary limit on
integer size.

> 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
systems.

>                                                          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.

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.

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
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.

Now, I don't personally think it's worth putting in a great deal of effort in
order to get that sort of information.


mathew