A Simple Turing Machine

Sat, 27 Aug 2011 10:00:00 GMT

I was searching for a simple way of experimenting with Turing machines for a small course I will give, but most of the software out there is either too complicated or has restrictions, like a predefined alphabet. So I hacked together a small turing machine:

(defun run-turing-machine
  (statelist current-state-name band bandptr)
   (let* ((bandlen (length band))
	  (cstate (cdr (assoc current-state-name statelist)))
	  (calpha (elt band bandptr))
	  (cdo (cdr (assoc calpha cstate)))
	  (do-write (car cdo))
	  (do-move (cadr cdo))
	  (do-goto (caddr cdo)))
     (setf (elt band bandptr) do-write)
     (incf bandptr (cond ((eql do-move 'R) 1)
                         ((eql do-move 'L) -1)
                         ((eql do-move 'S) 0)))
     (dotimes (i 70)
       (format t "~d" (elt band (+ i bandptr -35))))
     (format t "~%")
     (if (eql do-goto 'HALT) nil
	 (run-turing-machine statelist do-goto band bandptr))))

As it is very short, it is very easy to customize, so maybe it is the right thing for other people who are able to use lisp and want something similar. Which is why I am blogging about it, even though it is nothing special.

The code should be self-explanatory, as an example, the following is a machine which increases a dual number (consisting of 0s and 1s, bounded by 2 in the beginning and 3 in the end), and its output:

(run-turing-machine 
 '(
  (anf (0 2 S HALT) (1 2 S HALT) (2 2 R zu3))
  (zu3 (0 0 R zu3) (1 1 R zu3) (3 3 L letzteziffer))
  (letzteziffer (0 1 L andenanf) (1 0 L letzteziffer) (2 1 L anf))
  (andenanf (0 0 L andenanf) (1 1 L andenanf) (2 2 S HALT))
 )
 'anf
 (make-array '(100) :initial-contents
 '(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 2 1 1 1 1 1 3 0 0 0
   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)) 50)

0000000000000000000000000000000000211111300000000000000000000000000000
0000000000000000000000000000000002111113000000000000000000000000000000
0000000000000000000000000000000021111130000000000000000000000000000000
0000000000000000000000000000000211111300000000000000000000000000000000
0000000000000000000000000000002111113000000000000000000000000000000000
0000000000000000000000000000021111130000000000000000000000000000000000
0000000000000000000000000000002111113000000000000000000000000000000000
0000000000000000000000000000000211110300000000000000000000000000000000
0000000000000000000000000000000021110030000000000000000000000000000000
0000000000000000000000000000000002110003000000000000000000000000000000
0000000000000000000000000000000000210000300000000000000000000000000000
0000000000000000000000000000000000020000030000000000000000000000000000
0000000000000000000000000000000000001000003000000000000000000000000000
0000000000000000000000000000000000021000003000000000000000000000000000