Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!uflorida!haven!adm!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: <5785:Nov1519:19:5390@kramden.acf.nyu.edu> Date: 15 Nov 90 19:19:53 GMT References: <27477@megaron.cs.arizona.edu> <13350:Nov1419:44:2790@kramden.acf.nyu.edu> Organization: IR Lines: 25 If you have a program with a set of variables that enter a loop at time t, and continue to loop in a cycle of length l, then the method outlined will run the program in twice the memory at one-third speed minus housekeeping, and detect the loop between t and t + l, i.e., during its first cycle. That's all the practical solution to the halting problem does; interpret it as you wish. It's practical because the slowdown and memory waste are practical during debugging, and because t and l are relatively small in most practical cases. It's a solution to the halting problem because in the worst case it'll still detect the loop eventually, though I don't think these theoretical statements matter for the real world. In article gessel@carthage.cs.swarthmore.edu (Daniel Mark Gessel) writes: > > ]Here are two articles about the practical solution to the halting > > ]problem... > The Halting Problem is _not_ the cycle problem. The Computational Model is > a Turing Machine, not a computer with finite memory. See, this is what I mean about computer scientists. The computational model I work with is realistic---it's just my mental picture of what can be coded on lots of real machines. As I said before, it's finite. It has very, very little to do with a Turing machine. ---Dan