summaryrefslogtreecommitdiff
path: root/nix-turing/turingmachine.nix
blob: b8f159b6875f9ac938bffd330c19234bc04d9556 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
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;}