Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: Array references cannot be made optimal
Message-ID: <6045:Nov1519:34:2290@kramden.acf.nyu.edu>
Date: 15 Nov 90 19:34:22 GMT
References: <27498@megaron.cs.arizona.edu>
Organization: IR
Lines: 47

In article <27498@megaron.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes:
> In article  <13350:Nov1419:44:2790@kramden.acf.nyu.edu> Dan Bernstein writes:
> ]In practice, non-terminating programs enter a rather simple infinite
> ]loop.
  [ disagreement ]

Well, I can't remember ever debugging a non-terminating program that
*didn't* have a rather simple infinite loop, and I remember debugging
lots of programs where the loop was simple. Does your experience differ?
I'd be interested in seeing your example.

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

Not long ago in this thread I remarked that the halting problem is
solvable in practice. The response I got---from a computer scientist---
was religious disbelief. It doesn't take much thought to apply theory to
practice and put some reasonable bounds on the resources necessary to
discover a loop---but computer scientists *don't do it*.

> or it is a true solution to the problem of using finite state machines
> to detect non-termination on other finite state machines.

Yes, that is correct.

> But in this
> case it is not "practical", since there are many problems for which it
> will not terminate in a reasonable time.

Here we disagree about what problems come up in practice, and I'd be
interested in seeing your examples of those problems.

> ]> 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?

Just undecidability. Of course, if you were to believe some of the
people who argued with me in this group, you'd believe that sorting is
not linear in the number of bytes being sorted, that finding the optimal
pointer version of array code is decidable (NP, in fact---check out
Jim's articles over the past week), and also that the moon is made of
green cheese. Well, maybe not that last one.

---Dan