🚀 go-pugleaf

In article <13350:Nov1419:44:2790@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
   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

The Halting Problem is _not_ the cycle problem. The Computational Model is
a Turing Machine, not a computer with finite memory. 

The problem of determining whether or not a program goes into an infinite
loop is The Halting Problem, given that the language it is written in can
do dynamic allocation under the assumption that dynamic allocation will not
fail. If you assume that dynamic allocation will fail at some point, you
may be able to do some worthwhile analysis, and may be able to determine if a
program halts. I don't actually know. 

The Halting Problem is by definition abstract silliness.

Whether or not a computer program will stop depends exactly on your definition
of a computer program. The mathematical definition of an algorithm is 
equivalent to a turing machine, as far as anyone knows, and if you can
prove differently, you will become quite famous. For this definition of
an algorithm, the halting problem is unsolvable by a turing machine.

Dan

--
Daniel Mark Gessel                          Independent Software Consultant
Internet: gessel@cs.swarthmore.edu                  
I do not represent the opinions of Swarthmore College.