Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!elroy.jpl.nasa.gov!ncar!noao!arizona!gudeman
From: gudeman@cs.arizona.edu (David Gudeman)
Newsgroups: comp.lang.misc
Subject: Re: Array references cannot be made optimal
Message-ID: <27477@megaron.cs.arizona.edu>
Date: 14 Nov 90 15:16:50 GMT
Organization: U of Arizona CS Dept, Tucson
Lines: 19

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.  That, unless you include the entire
universe of things that might effect the program in the state (input
futures and such).  In that case it is a sufficient but still not
necessary condition for non-termination.

You could probably get a better approximate solution by a static
analysis of the program, and it would not effect run-time parameters.
-- 
					David Gudeman
Department of Computer Science
The University of Arizona        gudeman@cs.arizona.edu
Tucson, AZ 85721                 noao!arizona!gudeman