# 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;}