Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!asuvax!noao!arizona!gudeman
From: gudeman@cs.arizona.edu (David Gudeman)
Newsgroups: comp.lang.misc
Subject: Re: Will this *thread* ever halt?
Message-ID: <3410@optima.cs.arizona.edu>
Date: 21 May 91 19:49:35 GMT
Sender: news@cs.arizona.edu
Lines: 65

In article  <30814@dime.cs.umass.edu> victor yodaiken writes:
]... 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.

I argue that this is impossible in theory.  Infinite-loop detection
algorithms must almost certainly store some information about the
state space of the algorithm in question.  Furthermore, in the general
case this information must almost certainly require space on the order
of the size of the set of all possible states at a given point in the
program (see H1 below).

If so, the amount of information needed for at least some classes of
programs is huge.  So there are programs that would compile without
this analysis that cannot be compiled with this analysis.
Furthermore, due to the magnitude of the information that the
algorithm has to keep around, I'll bet that _most_ nontrivial programs
could not be analysed in this way.

Of course you can always reduce the amount of information you keep
around by compacting many states into a single approximating state.
If you do this you can greatly increase the set of programs you can
analyse, but your analysis is only approximate.  You can make the
approximation a safe one or a complete one: A safe approximation will
recognize all programs that definitely will _not_ halt.  A complete
approximation will recognize all programs that definitely _will_ halt.
I expect that these approximations can be made good enough to be very
useful.

Hypothesis H1:
  any algorithm, HALT(p) that solves the halting problem for p must in
general, for each point in p, encode at one time all the possible
states that might occur at that point in p.

Argument:
  suppose HALT(p1) returns TRUE.  Create program p2 by adding
somewhere the statement 

  if (F()) exit(); else for(;;);

where F is a function whose output depends on most of the current
state.  Then HALT must be able to determine whether F can ever
possibly answer 0 in order to tell if p2 halts.  To do this, in
general HALT must be able to encode all possible states that might
occur at this point.  It is possible to construct sets of states that
cannot be encoded by anything much smaller than the entire set of
states.

Any HALT algorighm that attempts to avoid this by only doing one state
at a time must in general deal with the possibility that HALT might
not terminate, since it is simulating the program being analysed.  The
same considerations apply to a program that works with subsets of the
total set of possible states.

You can use the trick of running p in two different virtual machines,
one going twice as fast as the other, and comparing states.  The
storage overhead of this is equal to twice the size of the states of
p.  In this case, there are still programs that will compile without
HALT that will not compile with HALT -- so _theoretically_ this
doesn't solve the problem.  And it isn't practical either, since if
there is an infinite loop, it may take gigayears to find it.
--
					David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudeman