summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorstuebinm2021-06-08 16:04:23 +0200
committerstuebinm2021-06-08 16:08:07 +0200
commit41cc0560362ad402a91e1eb006935865b7c42d97 (patch)
treeded65d7758cb2cf60522a3a6b3fcea03ae7a6720
parent4cba21106d13aa021b2757a3a550244a884cfccf (diff)
turing machine in nix
-rw-r--r--nix-turing/loop.nix26
-rw-r--r--nix-turing/turingmachine.nix84
2 files changed, 110 insertions, 0 deletions
diff --git a/nix-turing/loop.nix b/nix-turing/loop.nix
new file mode 100644
index 0000000..2849d6a
--- /dev/null
+++ b/nix-turing/loop.nix
@@ -0,0 +1,26 @@
+# defeats the recursion checks of nix and will cause it to
+# loop infinitely. well, almost, anyways.
+#
+# annoyingly, nix doesn't have tail recursion, so actually
+# it'll eventually terminate with a stack overflow.
+let
+ pkgs = import <nixpkgs> {};
+ writeTextVerbose = file: content: pkgs.stdenv.mkDerivation {
+ name = file;
+ src = pkgs.hello;
+ buildPhase = ''
+ echo ${pkgs.lib.escapeShellArg content} > $out
+ '';
+ installPhase = ''
+ echo wrote file to $name
+ '';
+ };
+ storefile = v: writeTextVerbose "nixfile" ''
+ {
+ x = ${toString v};
+ }
+ '';
+ loop = a:
+ let file = import (storefile a);
+ in if file.x == 1 then loop a else "done";
+in loop 1
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;}