turing_machine/bb6_tm_E00_notes.txt at master · jhuang97/turing_machine · GitHub

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
1RB0LE_1RC0RF_1RD---_0LA1RB_1RB1LE_1LD1RF

  0   1
A 1RB 0LE
B 1RC 0RF
C 1RD ---
D 0LA 1RB
E 1RB 1LE
F 1LD 1RF

shift rules:
1^n <E -> <E 1^n
F> 1^n -> 1^n F>

@dyuan01:
Let [0^inf, a, b, (c), d, e, 0^inf] be

0^inf 1^a 0 1^b 0 1^c <E 00 1^d 0 1^e 0^inf

(Every term to the right of the parenthesis until the infinite string of 0s must be positive, and some of the following rules use that fact)

Let me number dyuan's rules...
1. [...x, a, (b+2), c, y...] --> [...x, a+1, (b), c+1, y...]
2. [...x, a, (1), y...] --> [...x, (a), 1, y...]
3. [...x, a, (0), b+3, ... z+1, 0^inf] --> [...x, a+4, b+1, ... (z), 1, 0^inf]
4. [...x, a, (0), z+3, 0^inf] --> [...x, a+4, (z), 1, 0^inf]
5. [...x, a, (0), 2, b, y...] --> [...x, (a+3), b+1, y...]
6. [...x, (0), 1, ... z+1, 0^inf] --> Halt
7. [...x, a, (0), 1, 0^inf] --> [...x, (a+5), 0^inf]

repeat rule 1:
[...x, a, (2k), c, y...] --> [...x, a+k, (0), c+k, y...]  (k >= 1)

rules 1 and 2:
[...x, a, (2k+1), c, y...] --> [...x, a+k, (1), c+k, y...]  (k >= 1)
 --> [...x, (a+k), 1, c+k, y...]

verify each rule...
====
[...x, a, (b+2), c, y...] --> [...x, a+1, (b), c+1, y...]
this seems to be pretty local
0 1^b+2 <E 00
0 <E 1^b+2 00
1 B> 1^b+2 00
1 0 F> 1^b+1 00
1 0 1^b+1 F> 00
1 0 1^b+1 <D 10
1 0 1^b+1 B> 10
1 0 1^b+1 0 F> 0
1 0 1^b+1 0 <D 1
1 0 1^b+1 <A 0 1
1 0 1^b <E 00 1
this rule requires:
b >= 0
no reqs on a, c (can be zero or nonzero)

====
[...x, a, (1), y...] --> [...x, (a), 1, y...]

0 1 <E 00
0 <E 1 00
1 B> 1 00
1 0 F> 00
1 0 <D 10
1 <A 010
<E 00 10

no reqs on a, y

====
[...x, a, (0), b+3, ... z+1, 0^inf] --> [...x, a+4, b+1, ... (z), 1, 0^inf]

0 <E 00 1^b+3 0 ...
1 B> 00 1^b+3 0 ...
11 C> 0 1^b+3 0 ...
111 D> 1^b+3 0 ...
1111 B> 1^b+2 0 ...
1111 0 F> 1^b+1 0 ...
1111 0 1^b+1 F> 0 ...
1111 0 1^b+1 <D 1 ...
1111 0 1^b+1 B> 1 ...
1111 0 1^b+1 0 F> ...

so in general we have:
F> 1^b+1 0 -> 1^b+1 0 F>  (b >= 0)
thus F> can pass a bunch of positive terms on the right side represented by the ...

F> 1^z+1 0^inf
1^z+1 0 F> 0^inf
1^z+1 0 <D 1 0^inf
1^z+1 <A 0 1 0^inf
1^z <E 00 1 0^inf

no reqs on a
b, z >= 0
the ... between b+3 and z+1 can consist of >=0 term(s), each positive

====
[...x, a, (0), z+3, 0^inf] --> [...x, a+4, (z), 1, 0^inf]

0 <E 00 1^z+3 0 ...
1 B> 00 1^z+3 0 ...
11 C> 0 1^z+3 0 ...
111 D> 1^z+3 0 ...
1111 B> 1^z+2 0 ...
1111 0 F> 1^z+1 0 ...
..
F> 1^z+1 0^inf
1^z+1 0 F> 0^inf
1^z+1 0 <D 1 0^inf
1^z+1 <A 0 1 0^inf
1111 0 1^z <E 00 1 0^inf

no reqs on a
z >= 0

====
[...x, a, (0), 2, b, y...] --> [...x, (a+3), b+1, y...]
0 <E 00 11 0
1 B> 00 11 0
11 C> 0 11 0
111 D> 11 0
1111 B> 1 0
1111 0 F> 0
1111 0 <D 1
1111 <A 0 1
111 <E 00 1

no reqs on a, b, y

====
[...x, (0), 1, ... z+1, 0^inf] --> Halt
0 <E 00 1 0 1
1 B> 00 1 0 1
11 C> 0 1 0 1
111 D> 1 0 1
1111 B> 0 1
11111 C> 1 HALT

need the term to the right of 1 to be positive (nonzero)

====
[...x, a, (0), 1, 0^inf] --> [...x, (a+5), 0^inf]
0 <E 00 1 0^inf
1 B> 00 1 0^inf
11 C> 0 1 0^inf
111 D> 1 0^inf
1111 B> 0^inf
11111 C> 0^inf
111111 D> 0^inf
111111 <A 0^inf
11111 <E 00 0^inf

no reqs on a

-----
seems that replacing
self.right = vec![1];
with
self.right.clear();
self.right.push(1);
makes it more than 2x as fast.

Times for running it for 1e9 steps:
time: 13.326398587s
 1000000000: 192868005 424828196 86841165 9669494 (0) 89036
time: 13.282699586s
 1000000000: 192868005 424828196 86841165 9669494 (0) 89036

time: 5.279883552s
 1000000000: 192868005 424828196 86841165 9669494 (0) 89036
time: 5.175245289s
 1000000000: 192868005 424828196 86841165 9669494 (0) 89036
time: 5.071437791s
 1000000000: 192868005 424828196 86841165 9669494 (0) 89036

simulated up to
4127285048893: (5) 1 6 12 24 48 96 192 384 768 1536 3072 6144 12288 24576 49152 98304 196608 393216 786432 1572864 3145728 6291456 12582912 25165824 50331648 100663296 201326592 402653184 805306368 1610612736 3221225472 6442450944 12884901888 25769803776 51539607552 103079215104 206158430208 412316860416 824633720832 781301242340 391649288592 67756073042 150152143 25
5760000000001: 695124019532 695124019527 1390248039057 1200928761595 49385036550 (420943023) 1 1031
6770000000001: 405489168085 405489168080 3777913205978 144014640065 (3805947279) 1 276448
10380000000001: 3792422350050 2774889499521 677744572082 (12585863042) 1 351315 3
15760000000001: 8286762040884 2192830547474 (0) 485772102077 45436452875 1093471874 1434; 15.760%
21970000000001: 15053597264514 (289721161576) 1 122534849 19396; 21.970%
40030000000001: (23759352523250) 1 4012692600925 157470335331 1613522696 70523; 40.030%
47830000000001: 29886643351290 3298579679540 (0) 168833450036 10980379767 1672965; 47.830%
59220000000001: 30395687331965 10662936533149 235651572030 2691339483 (2268354) 1; 59.220%
81970320792024: (6) 1 7 14 28 56 112 224 448 896 1792 3584 7168 14336 28672 57344 114688 229376 458752 917504 1835008 3670016 7340032 14680064 29360128 58720256 117440512 234881024 469762048 939524096 1879048192 3758096384 7516192768 15032385536 30064771072 60129542144 120259084288 240518168576 481036337152 962072674304 1924145348608 3848290697216 7696581394432 9480887356124 13049499279513 14274447693553 4899793656160 38991918416 13530468
100000000000000: 7177690584002 39661507529556 19727946144835 3065161965630 (52192997903) 1 16563977 6