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: <6181:Nov1519:39:5490@kramden.acf.nyu.edu> Date: 15 Nov 90 19:39:54 GMT References: <3975:Nov1323:25:4390@kramden.acf.nyu.edu> <4279@goanna.cs.rmit.oz.au> Organization: IR Lines: 26 In article <4279@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: > In article <3975:Nov1323:25:4390@kramden.acf.nyu.edu>, > brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > > Here are two articles about the practical solution to the halting > > problem. > The technique referred to is commonly known as "Tortoise and Hare". > It's a very handy technique for programs that wander around graphs > and other finite data structures. Maybe computer science actually hasn't been regressing in Australia. Thanks for confirming that someone else in the world knows what everyone knew when the words ``computer science'' sounded funny... People who aren't familiar with loop detection should look in Knuth, exercises 3.1-6 and -7 (I think; I don't have the book handy). [ Eiffel termination tests ] > when you write a loop you can provide an expression whose value must decrease > on each iteration, while remaining non-negative. You can apply Q's invariants in similar ways. People who aren't familiar with these techniques should look in Knuth, chapter 1, the first section on Euclid's algorithm. ---Dan