Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Turing machine in Clojure
;;; -*- mode: clojure; coding: utf-8 -*-
;;; author: Roman Zaharov <zahardzhan@gmail.com>
(ns clojure.turing-machine.machine)
(in-ns 'clojure.turing-machine.machine)
(defn convert-rules [rules]
(apply conj [] (for [rule rules :let [[state read jump write move] rule]]
{:state state :read read :jump jump :write write :move move})))
(def UN+1 (convert-rules '[[0 0 0 0 R]
[0 1 1 1 R]
[1 0 0 1 S]
[1 1 1 1 R]]))
(defn machine [rules running state pos tape]
{:running running :state state :pos pos :tape tape :rules rules})
(defn step [{:as machine :keys [state pos tape rules running]}]
(if-not running machine
(some (fn [{:as rule :keys [write jump move]}]
(when (and (= (:state machine) (:state rule))
(= (tape pos) (:read rule)))
(assoc machine
:running (not= move 'S)
:state jump
:tape (assoc tape pos write)
:pos ((case move L dec, R inc, S inc) pos))))
rules)))
(defn run [machine]
(println (:tape machine))
(when (:running machine)
(recur (step machine))))
clojure.turing-machine.machine> (run (machine UN+1 true 0 0 [0 1 1 0 0]))
[0 1 1 0 0]
[0 1 1 0 0]
[0 1 1 0 0]
[0 1 1 0 0]
[0 1 1 1 0]
nil
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment