-
Notifications
You must be signed in to change notification settings - Fork 0
/
ali_bbeaver.ddd
136 lines (110 loc) · 3.22 KB
/
ali_bbeaver.ddd
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
import std.stdio;
import std.array;
import std.range;
enum Direction { L, R }
struct repeat(int Value) {
enum head = Value;
alias repeat!Value tail;
}
struct cons(int Head, Tail) {
enum head = Head;
alias Tail tail;
}
struct step(Direction d, Left, Right) {
static if (d == Direction.L) {
alias Left.tail left;
alias cons!(Left.head, Right) right;
} else static if (d == Direction.R) {
alias cons!(Right.head, Left) left;
alias Right.tail right;
} else {
static assert(false);
}
}
struct turing_machine(TuringMachine, Left, Right,
State = TuringMachine.initial_state)
if (!is (State == TuringMachine.final_state))
{
alias TuringMachine.transition_table!(Right.head, State) transition;
alias step!(transition.direction, Left,
cons!(transition.symbol, Right.tail)) after;
alias turing_machine!(TuringMachine, after.left, after.right,
transition.state) next;
alias next.final_left final_left;
alias next.final_right final_right;
}
struct turing_machine(TuringMachine, Left, Right,
State)
if (is (State == TuringMachine.final_state))
{
alias Left final_left;
alias Right final_right;
}
struct busy_beaver {
struct A {}
struct B {}
struct H {}
struct transition_table(int Sym, State) {
static if (Sym == 0) {
static if (is (State == busy_beaver.A)) {
enum symbol = 1;
enum direction = Direction.R;
alias B state;
} else static if (is (State == busy_beaver.B)) {
enum symbol = 1;
enum direction = Direction.L;
alias A state;
} else {
static assert(false);
}
} else static if (Sym == 1) {
static if (is(State == busy_beaver.A)) {
enum symbol = 1;
enum direction = Direction.L;
alias B state;
} else static if (is(State == busy_beaver.B)) {
enum symbol = 1;
enum direction = Direction.R;
alias H state;
} else {
static assert(false);
}
} else {
static assert(false);
}
}
alias A initial_state;
alias H final_state;
}
struct type_list_to_vector(Cons : cons!(Head, Tail), int Head, Tail) {
void opCall(ref int[] output) {
output ~= Head;
type_list_to_vector!Tail tl2v;
tl2v(output);
}
static auto opCall() {
type_list_to_vector!Cons tl2v;
return tl2v;
}
}
struct type_list_to_vector(Repeat : repeat!Value, int Value) {
void opCall(ref int[] output) {
output ~= Value;
}
}
void main() {
alias turing_machine!(busy_beaver, repeat!0, repeat!0) tm;
int[] tape;
type_list_to_vector!(tm.final_left)()(tape);
writef(".. %s ", tape.back);
foreach (i; retro(tape)) {
writef("%s ", i);
}
tape = tape.init;
type_list_to_vector!(tm.final_right)()(tape);
writef("*%s* ", tape.front);
foreach (i; tape[1 .. $]) {
writef("%s ", i);
}
writefln("%s ..", tape.back);
}