Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!psuvax1!swatsun!swatsun!gessel From: gessel@carthage.cs.swarthmore.edu (Daniel Mark Gessel) Newsgroups: comp.lang.misc Subject: Re: Array references cannot be made optimal Message-ID: Date: 14 Nov 90 22:58:31 GMT References: <27477@megaron.cs.arizona.edu> <13350:Nov1419:44:2790@kramden.acf.nyu.edu> Sender: news@cs.swarthmore.edu Organization: Swarthmore College, Swarthmore Pa. Lines: 51 In-Reply-To: brnstnd@kramden.acf.nyu.edu's message of 14 Nov 90 19:44:27 GMT Nntp-Posting-Host: carthage 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.