turing machine in nix

1 files changed, 84 insertions, 0 deletions

diff --git a/nix-turing/turingmachine.nix b/nix-turing/turingmachine.nix
new file mode 100644
index 0000000..b8f159b
--- /dev/null
+++ b/nix-turing/turingmachine.nix
@@ -0,0 +1,84 @@
+# a turing machine in Nix. Each step will produce a new
+# entry in the nix store containing the current band & state;
+# it terminates by deliberatly producing a syntax error.
+#
+# In other words, the question "will this file produce a
+# syntax error?" is equivalent to the halting problem.
+#
+# (this isn't acutally very suprising, you can do that
+# in any language that has an eval function, but it's
+# still fun to do)
+#
+# obviously nix will "cache" previous runs, so either
+# run a garbage collect or change a space somewhere
+# if you want to run the same machine more than once.
+let
+  pkgs = import <nixpkgs> {};
+  lib = pkgs.lib;
+  # state transitions and initial state for a busy beaver
+  # with two or three states (taken from wikipedia)
+  q0 = 1;
+  delta2 = {
+    "1" = {
+      "0" = { write = 1; move = "R"; next = 2; };
+      "1" = { write = 1; move = "L"; next = 3; };
+    };
+    "2" = {
+      "0" = { write = 1; move = "L"; next = 1; };
+      "1" = { write = 1; move = "R"; next = 2; };
+    };
+    "3" = {
+      "0" = { write = 1; move = "L"; next = 2; };
+      "1" = { write = 1; move = "R"; next = ";"; };
+    };
+  };
+  delta = {
+    "0" = {
+      "1" = { write = 1; move = "L"; next = 1; };
+      "0" = { write = 1; move = "R"; next = 1; };
+    };
+    "1" = {
+      "1" = { write = 0; move = "L"; next = 2; };
+      "0" = { write = 1; move = "L"; next = 0; };
+    };
+    "2" = {
+      "1" = { write = 1; move = "L"; next = 3; };
+      "0" = { write = 0; move = "R"; next = ";"; };
+    };
+    "3" = {
+      "1" = { write = 0; move = "R"; next = 0; };
+      "0" = { write = 1; move = "R"; next = 3; };
+    };
+  };
+  eval = name: string:
+    import (pkgs.writeText "${toString name}" string);
+  headOrEmpty = list:
+    with lib.lists;
+    if length list == 0 then 0 else head list;
+  tailOrEmpty = list:
+    with lib.lists;
+    if length list == 0 then [] else tail list;
+  logTape = {left, right, state}: goRight:
+    let printList = list:
+          lib.strings.concatStrings (map (t: (toString t) + " ") list);
+    in eval "now state ${toString state}, went ${if goRight then "right" else "left"}" ''
+      {
+        left = [ ${printList left} ];
+        right = [ ${printList right} ];
+        state = ${toString state};
+      }
+    '';
+  runTuring = {left, right, state}:
+    let
+      next = delta.${toString state}.${toString (headOrEmpty left)};
+      goRight = next.move == "R";
+      tape = if goRight then {
+        left = [(headOrEmpty right) next.write] ++ tailOrEmpty left;
+        right = tailOrEmpty right;
+      } else {
+        left = tailOrEmpty left;
+        right = [next.write] ++ right;
+      };
+    in runTuring (logTape (tape // {state = next.next;}) goRight);
+in
+runTuring {left = []; right = []; state = q0;}