Path: utzoo!censor!geac!torsqnt!lethe!yunexus!oz
From: oz@yunexus.yorku.ca (Ozan Yigit)
Newsgroups: comp.lang.misc
Subject: Re: Array references cannot be made optimal
Message-ID: <17583@yunexus.YorkU.CA>
Date: 15 Nov 90 15:25:12 GMT
References: <MISHA.90Nov7191750@just-right.ai.mit.edu> <23904:Nov905:22:5290@kramden.acf.nyu.edu> <11839@life.ai.mit.edu> <3975:Nov1323:25:4390@kramden.acf.nyu.edu>
Sender: news@yunexus.YorkU.CA
Organization: York U. Communications Research & Development
Lines: 36

In article <3975:Nov1323:25:4390@kramden.acf.nyu.edu>
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes on the halting
problem:

>		The practical solution is that we run the program
>on two machines with that number of states, one machine exactly twice as
>fast as the other; if the program loops in time t to t+u, then we will
>see the machines in exactly the same state at time 3t to 3t+3u.

This sounds exactly like an old lisp algorithm for determining whether or
ot a list is in fact circular. For example, the scheme code that determines
list-length while checking circularity looks like this:
	
	(define (list-length lst) (elen lst lst 0))
	(define (elen slow fast n)
	  (cond 
	   [(null? fast) 	n]
	   [(null? (cdr fast))  (1+ n)]
	   [(and (eq? fast slow) (not (= n 0))) "cycle in list"]
	   (else
	    (elen (cdr slow) (cddr fast) (+ n 2)))))
	
	;;; (set! foo '(a b c d e f g h i j))
	;;; (list-length foo)
	;;; (set-cdr! (list-tail foo 9) foo)
	;;; (list-length foo)


So, what is the big fuss about?

oz
---
Where the stream runneth smoothest,   | Internet: oz@nexus.yorku.ca 
the water is deepest.  - John Lyly    | UUCP: utzoo/utai!yunexus!oz