Студеною зимней порою я коротал вечера за чтением популярной книжки Пенроуза «Новый ум короля», в которой математик рассказывал «о компьютерах, мышлении и законах физики». Это было увлекательное чтиво, местами сдобренное доброй пачкой формул из разных областей физики и математики.

Первая глава была посвящена машине Тьюринга и λ-исчислению. Тогда я как раз только начал изучать Clojure, и вот однажды вечером на меня снизошло толи вдохновение толи смертная скука — от нечего делать я решил написать маленькую машину Тьюринга. Часом позже машина была готова. Она получилась очень маленькая и в целом, достаточно хорошая — на следующее утро я очень удивился увидев свой твит с ссылкой на github.gist на планете Clojure.

Я не большой любитель формальностей компьютерных наук, поэтому опишу суть по-простому. Итак, машина Тьюринга — это штуковина, которая пребывает в одном из множества состояний и управляется правилами перехода между ними; ездит взад-вперед по ленте с нулями и единицами и по ходу своей езды переписывает ленту до тех пор пока не остановится или не зависнет (и тогда уже никогда не остановится).

Чудесная возможность зависнуть при удачном сочетании правил перехода и нулей-единиц на ленте делает машину Тьюринга настоящим компьютером, а заодно позволяет вычислить ею все, что можно вычислить на любом другом компьютере.

UN+1 — это набор правил для машины которая добавляет к последовательности единиц на ленте одну единицу справа. Правила к ней я задал в формате который использует Пенроуз в своей книге. Функция convert-rules преобразует правила в более удобный для Clojure формат.

(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]]))

Здесь 1ый столбик — это номер состояния, 2ой — цифра которую прочла машина с ленты, 3ий — в какое состояние машина должна перейти, 4ый — что она должна записать на ленту, 5ый — команда шага: R (сдвинуться на ленте вправо), L (сдвинуться на ленте влево), N (остаться на месте) и S (остановиться).

Сама машина задается таблицей правил rules, индикатором активности running, номером текущего состояния state, позицией на ленте pos, и лентой по которой она ездит tape.

(defn machine [rules running state pos tape] 
  {:rules rules :running running :state state :pos pos :tape tape})

На каждом шаге своей работы машина читает ячейку ленты и изменяет свое состояние соответственно таблице правил.

(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, N identity, S inc) pos))))
                rules)))

Запуск машины может привести к зависанию, так что надо быть осторожнее.

(defn run [machine]
  (println (:tape machine))
  (when (:running machine) 
    (recur (step 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

Как и ожидалось, машина дописала единичку справа.