Path: utzoo!attcan!uunet!wuarchive!zaphod.mps.ohio-state.edu!ncar!noao!amethyst!arizona!gudeman
From: gudeman@cs.arizona.edu (David Gudeman)
Newsgroups: comp.lang.misc
Subject: Re: Array references cannot be made optimal
Message-ID: <27498@megaron.cs.arizona.edu>
Date: 15 Nov 90 00:43:15 GMT
Organization: U of Arizona CS Dept, Tucson
Lines: 68

In article  <13350:Nov1419:44:2790@kramden.acf.nyu.edu> Dan Bernstein writes:
]In article <27477@megaron.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes:
]> This isn't a solution to the halting problem, it's a solution to the
]> problem of determining whether a program ever enters the same state
]> twice...
]
]More abstract silliness. Perhaps you forgot that the computational model
]is finite. The halting problem *is* the cycle problem.
]
]In practice, non-terminating programs enter a rather simple infinite
]loop.

I was objecting on practical grounds, not theoretical ones.  Since, as
you point out, a real computer is finite, the halting problem is
theoreticaly solvable for them, but it is not clear that you have
presented a _practical_ solution.  It is not the case that all forms
of non-termination involve "rather simple infinite loops", nor is it
clear that this is the case in practice either.  (Such forms of
non-termination, by the way, are usually easy to find by static
analysis.)

In _practice_, a computer program has a huge number of states, and
there is no reason to suppose that an infinite loop will cover only a
small set of states.  Even if the loop is doing something as simple as
incrementing a few variables, say n, then the number of states in a
cycle is on the order of MaxInteger^n.  How long, on average, do you
think it will take to detect loops in such a set of states?

Your method can take arbitrarily long to detect an infinite loop, and
in _practice_ if it takes too long it may as well never terminate.  So
the _practical_ effect of your method is that it will sometimes
terminate with an answer ("infinite loop" or "no infinite loop") and
will sometimes never terminate.  Any theoretician can tell you that
such a test is possible, so I don't see any justification behind your
negative comments about computer science.  It seems to me that
practice follows theory quite closely here.

This is not to suggest that it is worthless to do anything about
infinite loops.  There are approximate solutions known, but most
people are careful to observe that the solutions are approximate, and
only detect some subset of non-terminating programs.  Saying that you
have a "practical solution to the halting problem" is deliberately
antagonistic, as well as incorrect.  Your solution is either a
practical partial way to detect _some_ non-terminating programs, in
which case it is not a "solution" in the technical sense of the word,
or it is a true solution to the problem of using finite state machines
to detect non-termination on other finite state machines.  But in this
case it is not "practical", since there are many problems for which it
will not terminate in a reasonable time.

]> You could probably get a better approximate solution by a static
]> analysis of the program,
]
]No, you cannot, just as you cannot optimize arrays into pointers by a
]static analysis.

Are you suggesting that there is some connection here?

And would you care to give some references to support this statement?
(Not the connection, the assertion that you cannot get a better
approximation by static analysis.)  I'm curious as to how you are
defining "better" in such a way that you can state this as a fact
rather than as an opinion.
-- 
					David Gudeman
Department of Computer Science
The University of Arizona        gudeman@cs.arizona.edu
Tucson, AZ 85721                 noao!arizona!gudeman