Path: utzoo!utgpu!news-server.csri.toronto.edu!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: <8699:Nov1522:27:4590@kramden.acf.nyu.edu> Date: 15 Nov 90 22:27:45 GMT References: <5785:Nov1519:19:5390@kramden.acf.nyu.edu> <11897@life.ai.mit.edu> Organization: IR Lines: 46 In article <11897@life.ai.mit.edu> misha@just-right.ai.mit.edu (Mike Bolotski) writes: > In article <5785:Nov1519:19:5390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >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 fine, Dan. What if the cycle length is several millenia? Then it will be detected in at most several times three millenia. But I've never seen this happen *in practice*. Have you ever debugged a program to find an infinite loop that would take such a long time, or are you just arguing for the sake of argument? A few examples of the former wouldn't diminish the practical value of the solution, but I'd be interested in seeing them anyway. > >the worst case it'll still detect the loop eventually, though I don't > >think these theoretical statements matter for the real world. > The real world being defined as your experience alone, is it? Again, I invite comments from anyone whose experience differs. I haven't seen any such comments yet. > >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 > No need to apologize for your limitations, Dan. I insist upon apologizing. I simply cannot bring myself to imagine a computer with an infinite amount of memory. When I imagine a byte being sent to memory, the computer explodes and settles into dust. When I picture a Turing machine, it has a lot of tape stretching off into the distance, but I just can't see each and every bit on the tape all at once. Maybe this is just because in my finite experience I've never seen how an infinite computer would work, or where it would be stored. I'm also a firm believer in propositional set theory, if you're mathematically inclined enough to know what that is. Tarski's last book (with Givant) is my bible on these matters. If you in your infinite wisdom would deign to explain to me how to visualize the infinitely powerful computer of yours, I'd be eternally grateful. No, scrap that, I'd be finitely grateful. ---Dan