Comment: This TM produces >3.7x10^6518 nonzeros in >5.2x10^13036 steps. Comment: This is the currently best known 3x4 TM
| State | on 0 |
on 1 |
on 2 |
on 3 |
on 0 | on 1 | on 2 | on 3 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Move | Goto | Move | Goto | Move | Goto | Move | Goto | |||||||||
| A | 1RB | 1RA | 2LB | 3LA | 1 | right | B | 1 | right | A | 2 | left | B | 3 | left | A |
| B | 2LA | 0LB | 1LC | 1LB | 2 | left | A | 0 | left | B | 1 | left | C | 1 | left | B |
| C | 3RB | 3RC | 1RH | 1LC | 3 | right | B | 3 | right | C | 1 | right | H | 1 | left | C |
The same TM just simple.
The same TM with repetitions reduced.
The same TM with tape symbol exponents.
Simulation is done as 1-macro machine.
The same TM as 1-macro machine with pure additive config-TRs.
Pushing initial machine.
Pushing macro factor 1.
Steps BasSteps BasTpos Tape contents
0 0 0 A>
1 1 1 1 B>
2 2 0 1 <A 2
3 3 1 1 A> 2
4 4 0 1 <B 2
5 5 -1 <B 0 2
6 6 -2 <A 2 0 2
7 7 -1 1 B> 2 0 2
8 8 -2 1 <C 1 0 2
9 9 -1 3 C> 1 0 2
10 10 0 32 C> 0 2
11 11 1 33 B> 2
12 12 0 33 <C 1
13 15 -3 <C 14
14 16 -2 3 B> 14
15 17 -3 3 <B 0 13
16 18 -4 <B 1 0 13
17 19 -5 <A 2 1 0 13
18 20 -4 1 B> 2 1 0 13
19 21 -5 1 <C 12 0 13
20 22 -4 3 C> 12 0 13
21 24 -2 33 C> 0 13
22 25 -1 34 B> 13
23 26 -2 34 <B 0 12
24 30 -6 <B 14 0 12
25 31 -7 <A 2 14 0 12
26 32 -6 1 B> 2 14 0 12
27 33 -7 1 <C 15 0 12
28 34 -6 3 C> 15 0 12
29 39 -1 36 C> 0 12
30 40 0 37 B> 12
31 41 -1 37 <B 0 1
32 48 -8 <B 17 0 1
33 49 -9 <A 2 17 0 1
34 50 -8 1 B> 2 17 0 1
35 51 -9 1 <C 18 0 1
36 52 -8 3 C> 18 0 1
37 60 0 39 C> 0 1
38 61 1 310 B> 1
39 62 0 310 <B
40 72 -10 <B 110
41 73 -11 <A 2 110
42 74 -10 1 B> 2 110
43 75 -11 1 <C 111
44 76 -10 3 C> 111
45 87 1 312 C>
46 88 2 313 B>
47 89 1 313 <A 2
48 102 -12 <A 313 2
49 103 -11 1 B> 313 2
50 104 -12 1 <B 1 312 2
51 105 -13 <B 0 1 312 2
52 106 -14 <A 2 0 1 312 2
53 107 -13 1 B> 2 0 1 312 2
54 108 -14 1 <C 1 0 1 312 2
55 109 -13 3 C> 1 0 1 312 2
56 110 -12 32 C> 0 1 312 2
57 111 -11 33 B> 1 312 2
58 112 -12 33 <B 0 312 2
59 115 -15 <B 13 0 312 2
60 116 -16 <A 2 13 0 312 2
61 117 -15 1 B> 2 13 0 312 2
62 118 -16 1 <C 14 0 312 2
63 119 -15 3 C> 14 0 312 2
64 123 -11 35 C> 0 312 2
65 124 -10 36 B> 312 2
66 125 -11 36 <B 1 311 2
67 131 -17 <B 17 311 2
68 132 -18 <A 2 17 311 2
69 133 -17 1 B> 2 17 311 2
70 134 -18 1 <C 18 311 2
71 135 -17 3 C> 18 311 2
72 143 -9 39 C> 311 2
73 144 -10 39 <C 1 310 2
74 153 -19 <C 110 310 2
75 154 -18 3 B> 110 310 2
76 155 -19 3 <B 0 19 310 2
77 156 -20 <B 1 0 19 310 2
78 157 -21 <A 2 1 0 19 310 2
79 158 -20 1 B> 2 1 0 19 310 2
80 159 -21 1 <C 12 0 19 310 2
81 160 -20 3 C> 12 0 19 310 2
82 162 -18 33 C> 0 19 310 2
83 163 -17 34 B> 19 310 2
84 164 -18 34 <B 0 18 310 2
85 168 -22 <B 14 0 18 310 2
86 169 -23 <A 2 14 0 18 310 2
87 170 -22 1 B> 2 14 0 18 310 2
88 171 -23 1 <C 15 0 18 310 2
89 172 -22 3 C> 15 0 18 310 2
90 177 -17 36 C> 0 18 310 2
91 178 -16 37 B> 18 310 2
92 179 -17 37 <B 0 17 310 2
93 186 -24 <B 17 0 17 310 2
94 187 -25 <A 2 17 0 17 310 2
95 188 -24 1 B> 2 17 0 17 310 2
96 189 -25 1 <C 18 0 17 310 2
97 190 -24 3 C> 18 0 17 310 2
98 198 -16 39 C> 0 17 310 2
99 199 -15 310 B> 17 310 2
100 200 -16 310 <B 0 16 310 2
101 210 -26 <B 110 0 16 310 2
102 211 -27 <A 2 110 0 16 310 2
103 212 -26 1 B> 2 110 0 16 310 2
104 213 -27 1 <C 111 0 16 310 2
105 214 -26 3 C> 111 0 16 310 2
106 225 -15 312 C> 0 16 310 2
107 226 -14 313 B> 16 310 2
108 227 -15 313 <B 0 15 310 2
109 240 -28 <B 113 0 15 310 2
110 241 -29 <A 2 113 0 15 310 2
111 242 -28 1 B> 2 113 0 15 310 2
112 243 -29 1 <C 114 0 15 310 2
113 244 -28 3 C> 114 0 15 310 2
114 258 -14 315 C> 0 15 310 2
115 259 -13 316 B> 15 310 2
116 260 -14 316 <B 0 14 310 2
117 276 -30 <B 116 0 14 310 2
118 277 -31 <A 2 116 0 14 310 2
119 278 -30 1 B> 2 116 0 14 310 2
120 279 -31 1 <C 117 0 14 310 2
121 280 -30 3 C> 117 0 14 310 2
122 297 -13 318 C> 0 14 310 2
123 298 -12 319 B> 14 310 2
124 299 -13 319 <B 0 13 310 2
125 318 -32 <B 119 0 13 310 2
126 319 -33 <A 2 119 0 13 310 2
127 320 -32 1 B> 2 119 0 13 310 2
128 321 -33 1 <C 120 0 13 310 2
129 322 -32 3 C> 120 0 13 310 2
130 342 -12 321 C> 0 13 310 2
131 343 -11 322 B> 13 310 2
132 344 -12 322 <B 0 12 310 2
133 366 -34 <B 122 0 12 310 2
134 367 -35 <A 2 122 0 12 310 2
135 368 -34 1 B> 2 122 0 12 310 2
136 369 -35 1 <C 123 0 12 310 2
137 370 -34 3 C> 123 0 12 310 2
138 393 -11 324 C> 0 12 310 2
139 394 -10 325 B> 12 310 2
140 395 -11 325 <B 0 1 310 2
141 420 -36 <B 125 0 1 310 2
142 421 -37 <A 2 125 0 1 310 2
143 422 -36 1 B> 2 125 0 1 310 2
144 423 -37 1 <C 126 0 1 310 2
145 424 -36 3 C> 126 0 1 310 2
146 450 -10 327 C> 0 1 310 2
147 451 -9 328 B> 1 310 2
148 452 -10 328 <B 0 310 2
149 480 -38 <B 128 0 310 2
150 481 -39 <A 2 128 0 310 2
151 482 -38 1 B> 2 128 0 310 2
152 483 -39 1 <C 129 0 310 2
153 484 -38 3 C> 129 0 310 2
154 513 -9 330 C> 0 310 2
155 514 -8 331 B> 310 2
156 515 -9 331 <B 1 39 2
157 546 -40 <B 132 39 2
158 547 -41 <A 2 132 39 2
159 548 -40 1 B> 2 132 39 2
160 549 -41 1 <C 133 39 2
161 550 -40 3 C> 133 39 2
162 583 -7 334 C> 39 2
163 584 -8 334 <C 1 38 2
164 618 -42 <C 135 38 2
165 619 -41 3 B> 135 38 2
166 620 -42 3 <B 0 134 38 2
167 621 -43 <B 1 0 134 38 2
168 622 -44 <A 2 1 0 134 38 2
169 623 -43 1 B> 2 1 0 134 38 2
170 624 -44 1 <C 12 0 134 38 2
171 625 -43 3 C> 12 0 134 38 2
172 627 -41 33 C> 0 134 38 2
173 628 -40 34 B> 134 38 2
174 629 -41 34 <B 0 133 38 2
175 633 -45 <B 14 0 133 38 2
176 634 -46 <A 2 14 0 133 38 2
177 635 -45 1 B> 2 14 0 133 38 2
178 636 -46 1 <C 15 0 133 38 2
179 637 -45 3 C> 15 0 133 38 2
180 642 -40 36 C> 0 133 38 2
181 643 -39 37 B> 133 38 2
182 644 -40 37 <B 0 132 38 2
183 651 -47 <B 17 0 132 38 2
184 652 -48 <A 2 17 0 132 38 2
185 653 -47 1 B> 2 17 0 132 38 2
186 654 -48 1 <C 18 0 132 38 2
187 655 -47 3 C> 18 0 132 38 2
188 663 -39 39 C> 0 132 38 2
189 664 -38 310 B> 132 38 2
190 665 -39 310 <B 0 131 38 2
191 675 -49 <B 110 0 131 38 2
192 676 -50 <A 2 110 0 131 38 2
193 677 -49 1 B> 2 110 0 131 38 2
194 678 -50 1 <C 111 0 131 38 2
195 679 -49 3 C> 111 0 131 38 2
196 690 -38 312 C> 0 131 38 2
197 691 -37 313 B> 131 38 2
198 692 -38 313 <B 0 130 38 2
199 705 -51 <B 113 0 130 38 2
200 706 -52 <A 2 113 0 130 38 2
Lines: 201
Top steps: 200
Macro steps: 200
Basic steps: 706
Tape index: -52
nonzeros: 53
log10(nonzeros): 1.724
log10(steps ): 2.849
Input to awk program:
gohalt 1
nbs 4
T 3-state 4-symbol #i (T.J. & S. Ligocki)
: >3.7x10^6518 >5.2x10^13036
C This is the currently best known 3x4 TM
5T 1RB 1RA 2LB 3LA 2LA 0LB 1LC 1LB 3RB 3RC 1RH 1LC
L 60
M 201
pref sim
machv Lig34_i just simple
machv Lig34_i-r with repetitions reduced
machv Lig34_i-1 with tape symbol exponents
machv Lig34_i-m as 1-macro machine
machv Lig34_i-a as 1-macro machine with pure additive config-TRs
iam Lig34_i-m
mtype 1
mmtyp 1
r 1
H 1
mac 0
E 2
sympr
HM 1
date Tue Jul 6 22:13:57 CEST 2010
edate Tue Jul 6 22:13:57 CEST 2010
bnspeed 1
short 7
Constructed by: $Id: tmJob.awk,v 1.34 2010/05/06 18:26:17 heiner Exp $
$Id: basics.awk,v 1.1 2010/05/06 17:24:17 heiner Exp $
$Id: htSupp.awk,v 1.14 2010/07/06 19:48:32 heiner Exp $
$Id: mmSim.awk,v 1.34 2005/01/09 22:23:28 heiner Exp $
$Id: bignum.awk,v 1.34 2010/05/06 17:58:14 heiner Exp $
$Id: varLI.awk,v 1.11 2005/01/15 21:01:29 heiner Exp $
bignum signature: LEN={S++:9 U++:9 S+:8 U+:8 S*:4 U*:4} DONT: y i o;
Start: Tue Jul 6 22:13:57 CEST 2010