🚀 go-pugleaf

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