Path: utzoo!attcan!uunet!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: <13350:Nov1419:44:2790@kramden.acf.nyu.edu>
Date: 14 Nov 90 19:44:27 GMT
References: <27477@megaron.cs.arizona.edu>
Organization: IR
Lines: 25

In article <27477@megaron.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes:
> In article  <3975:Nov1323:25:4390@kramden.acf.nyu.edu> Dan Bernstein writes:
> ]Here are two articles about the practical solution to the halting
> ]problem...
> 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--which is neither a sufficient nor necessary condition for a
> program to be non-terminating.

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. But this is irrelevant to the theoretical correctness of the
method.

I advise that you read the articles, which allude to these non-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.

---Dan