Turing machine implementation from Clojure TO 2022-04-19

turing.clj

(ns turing)

(def dirs
  {:l dec
   :r inc})

(defn move
  [machine dir]
  (update machine :pos (dirs dir)))

(defn read-program
  [machine state sym]
  (get (:program machine) [state sym]))

(defn read-state
  [machine]
  (:state machine))

(defn read-sym
  [machine]
  (get (:tape machine) (:pos machine)))

(defn write-state
  [machine state]
  (assoc machine :state state))

(defn write-sym
  [machine sym]
  (update machine :tape assoc (:pos machine) sym))


(defn step
  [machine]
  ; read current symbol
  ; look up [current state, current symbol] in program
  ; update with write, move, set-state based on result

  (if-let [[state sym dir] (read-program machine (read-state machine) (read-sym machine))]
    (-> machine
        (write-state state)
        (write-sym sym)
        (move dir)
        (update :steps inc))
    machine))


(defn run
  [machine]
  (->> (iterate step machine)
       (partition 2 1)
       (drop-while (fn [[a b]]
                     (not= a b)))
       first
       first))

(defn run-n
  [machine n]
  (->> (iterate step machine)
       (drop n)
       first))

(defn print-machine
  [machine]
  (let [tape (:tape machine)
        p (apply min (keys tape))
        q (apply max (keys tape))
        tape-cells (for [i (range p (inc q))]
                     (str "|" (or (get tape i) " ")))]

    (doseq [cells (partition-all 40 tape-cells)]
      (println (apply str cells)))
    #_(doseq [i (range p (inc q))]
      (print (str "|" (or (get tape i) " "))))
    #_(println "|")
    ;(println "Tape: " (:tape machine))
    (println "Count:" (count (:tape machine)))
    (println "State:" (:state machine))
    (println "Pos:  " (:pos machine))
    (println "Steps:" (:steps machine))

    ))


(def bb-4-machine
  {:pos 0
   :tape {}
   :state :a
   :steps 0
   :program {
             [:a nil] [:b 1 :r]
             [:b nil] [:a 1 :l]
             [:a 1]   [:b 1 :l]
             [:b 1]   [:c nil :l]
             [:c 1]   [:d 1 :l]
             [:d nil] [:d 1 :r]
             [:d 1]   [:a nil :r]
             [:c nil] [:halt 1 :r]
             }
   })

(def bb-5-machine
  {:pos 0
   :tape {}
   :state :a
   :steps 0
   :program {
             [:a nil] [:b 1 :r]
             [:a 1]   [:a 1 :r]
             [:b nil] [:c 1 :l]
             [:b 1]   [:b 1 :l]
             [:c nil] [:d 1 :r]
             [:c 1]   [:d 1 :l]
             [:d nil] [:a 1 :r]
             [:d 1]   [:e 1 :l]
             [:e nil] [:halt 1 :r]
             [:e 1]   [:c nil :l]
             }
   })

(def bb-5-machine'
  {:pos 0
   :tape {}
   :state :a
   :steps 0
   :program {
             [:a nil] [:b 1 :r]
             [:a 1]   [:a 1 :r]
             [:b nil] [:c 1 :l]
             [:b 1]   [:d 1 :r]
             [:c nil] [:a 1 :l]
             [:c 1]   [:c 1 :l]
             [:d nil] [:halt 1 :r]
             [:d 1]   [:e nil :r]
             [:e nil] [:c 1 :l]
             [:e 1]   [:b 1 :r]
             }
   })


#_(-> bb-5-machine'
      run
      print-machine)

#_(time (-> bb-5-machine'
            (run-n 1300)
            (print-machine)))

#_(run-n machine 100)

#_(step machine)

#_(-> machine
      step
      step
      step
      )