turing-machine.clj

(ns turing-machine.core)

;; TURING MACHINE:
;;    - non-empty set of states
;;    - set of the tape alphabet/symbols
;;    - the blank symbol
;;    - the set of input symbols
;;    - the initial state
;;    - the set of final or accepting states.
;;    - the transition function, where L is left shift, R is right shift.

;; Busy beaver is an example of a spec.
(def busy-beaver {:states        #{:A :B :C :HALT}
                  :alphabet      #{0 1}
                  :blank         0
                  :input         '(1)
                  :initial-state :A
                  :accept-states #{:HALT}
                  :transition-f {:A {0 {:write 1 :move :R :next :B}
                                     1 {:write 1 :move :L :next :C}}
                                 :B {0 {:write 1 :move :L :next :A}
                                     1 {:write 1 :move :R :next :B}}
                                 :C {0 {:write 1 :move :L :next :B}
                                     1 {:write 1 :move :R :next :HALT}}}})

(defn move-head
  "direction (i.e. :R or :L) left right -> [left right]"
  [direction l r]
  (assert (contains? #{:L :R} direction))

  (if (= :L direction)
    [(cons (first r) l) (rest r)]
    [(rest l) (cons (first l) r)]))

(defn print-step
  [counter l r]
  (println counter "\t"
           (map #(if (= 0 %) " " %)
                (concat (reverse (take 10 l)) (take 10 r)))))

(defn turing-machine
  "spec -> tape.
  Takes a spec for a Turing Machine and returns the tape at the last step. A
  tap is a pair [left right] representing the left and right portions of the
  tape. Both left and right are infinite sequences. Also, prints the tape at
  each step in the process."
  [spec]
  (let [transition (spec :transition-f)]
    (loop [curr-state (:initial-state spec)
           l (repeat (:blank spec))
           r (concat (:input spec) (repeat (:blank spec)))
           counter 1]
      (print-step counter l r)

      (if (contains? (spec :accept-states) curr-state)
        [l r]
        (let [curr-letter (first r)
              action ((curr-state transition) curr-letter)
              r (cons (:write action) (rest r))
              [l r] (move-head (:move action) l r)]
          (recur (:next action) l r (inc counter)))))))

(defn -main [& args]
  (turing-machine busy-beaver))