[plt-scheme] Effect of caching using hash-tables vs vectors

On 3/20/07, Paulo J. Matos <pocm at soton.ac.uk> wrote:
>
> PS. Just before clicking the send button I had a quick thought about
> the collatz sequence. Isn't it true that solving the halting problem
> would prove the collatz conjecture?

It would certainly decide it one way or the other.

Here's an unusual version of the collatz program written in
Common Lisp:

(defun kernel (s i)
  (list (not (car s))
        (if (car s)
            (cadr s)
          (cons i (cadr s)))
        (cons 'y (cons i (cons 'z (caddr s))))))

(defconstant k0 '(t () (x)))

(defun mystery (list)
  (let ((result (reduce #'kernel list :initial-value k0)))
    (cond ((null (cadr result)))
          ((car result) (mystery (cadr result)))
          (t (mystery (caddr result))))))

A reasonable Scheme translation is left as an exercise to the
reader.

-- 
~jrm