チューリングマシン

言語:Emacs Lisp

(defun turing (input)
  (let ((tape (make-list 16 0))
	(head '(0 0))
	(prog nil))
    
    (defun readhead ()
      (elt tape (car head)))
    (defun writehead (x)
      (setf (elt tape (car head)) x))
    (defun movehead (x)
      (if (equal x 'R)
	  (setf (car head) (1+ (car head)))
	(setf (car head) (1- (car head)))))
    (defun memoryhead (x)
      (setf (cadr head) x))
    (defun printf ()
      tape)
    (defun main ()
      (setq prog input)
      (setq head '(0 0))
      (while (not (equal (cadr head) nil))
	  (dolist (x prog)
	    (if (equal (cadr head) (car x))
		(if (equal (readhead) (elt x 1))
		    (progn (writehead (elt x 3))
			   (memoryhead (elt x 4))
			   (movehead (elt x 2))))))))
    (main)
    (printf)))

謎のバグがあって、一回目の評価だけしか正しくないです。
headの初期化と関係してるっぽいけど、よくわからない・・・

例

(turing '((0 0 R 1 1) (1 0 R 2 nil)))
(1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0)