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