Comment: This TM produces 90'604 nonzeros in 8'619'024'596 steps.
| State | on 0 |
on 1 |
on 2 |
on 3 |
on 4 |
on 0 | on 1 | on 2 | on 3 | on 4 | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Move | Goto | Move | Goto | Move | Goto | Move | Goto | Move | Goto | |||||||||||
| A | B1R | A3L | B1L | A1R | A3R | 1 | right | B | 3 | left | A | 1 | left | B | 1 | right | A | 3 | right | A |
| B | B2L | A3L | A3R | B4R | Z1R | 2 | left | B | 3 | left | A | 3 | right | A | 4 | right | B | 1 | right | Z |
The same TM just simple.
The same TM with repetitions reduced.
The same TM with tape symbol exponents.
The same TM as 1-bck-macro machine.
Simulation is done as 1-bck-macro machine with pure additive config-TRs.
Pushing initial machine.
Pushing macro factor 1.
Pushing BCK machine.
Steps BasSteps BasTpos Tape contents
0 0 0 (0)A>
1 1 1 (1)B>
2 3 -1 <A(3) 2
3 5 1 1 (4)B> 2
4 6 2 1 4 (3)A>
5 7 3 1 4 3 (1)B>
6 9 1 1 4 3 <A(3) 2
7 11 3 1 4 1 (1)A> 2
8 13 1 1 4 1 <A(3) 1
9 14 0 1 4 <A(3) 3 1
10 16 2 1 3 (1)A> 3 1
11 17 3 1 3 1 (1)A> 1
12 19 1 1 3 1 <A(3) 3
13 20 0 1 3 <A(3) 32
14 22 2 12 (1)A> 32
15 24 4 14 (1)A>
16 25 5 15 (1)B>
17 27 3 15 <A(3) 2
18 32 -2 <A(3) 35 2
19 34 0 1 (4)B> 35 2
20 39 5 1 45 (4)B> 2
21 40 6 1 46 (3)A>
22 41 7 1 46 3 (1)B>
23 43 5 1 46 3 <A(3) 2
24 45 7 1 46 1 (1)A> 2
25 47 5 1 46 1 <A(3) 1
26 48 4 1 46 <A(3) 3 1
27 50 6 1 45 3 (1)A> 3 1
28 51 7 1 45 3 1 (1)A> 1
29 53 5 1 45 3 1 <A(3) 3
30 54 4 1 45 3 <A(3) 32
31 56 6 1 45 1 (1)A> 32
32 58 8 1 45 13 (1)A>
33 59 9 1 45 14 (1)B>
34 61 7 1 45 14 <A(3) 2
35 65 3 1 45 <A(3) 34 2
36 67 5 1 44 3 (1)A> 34 2
37 71 9 1 44 3 14 (1)A> 2
38 73 7 1 44 3 14 <A(3) 1
39 77 3 1 44 3 <A(3) 34 1
40 79 5 1 44 1 (1)A> 34 1
41 83 9 1 44 15 (1)A> 1
42 85 7 1 44 15 <A(3) 3
43 90 2 1 44 <A(3) 36
44 92 4 1 43 3 (1)A> 36
45 98 10 1 43 3 16 (1)A>
46 99 11 1 43 3 17 (1)B>
47 101 9 1 43 3 17 <A(3) 2
48 108 2 1 43 3 <A(3) 37 2
49 110 4 1 43 1 (1)A> 37 2
50 117 11 1 43 18 (1)A> 2
>> Try to prove a PA-CTR with 2 Vars...
0 0 0 [*]* 44+V(2) 11+V(1) (1)A> 2
1 2 -2 [*]* 44+V(2) 11+V(1) <A(3) 1
2 3+V(1) -3+-1*V(1) [*]* 44+V(2) <A(3) 31+V(1) 1
3 5+V(1) -1+-1*V(1) [*]* 43+V(2) 3 (1)A> 31+V(1) 1
4 6+2*V(1) 0 [*]* 43+V(2) 3 11+V(1) (1)A> 1
5 8+2*V(1) -2 [*]* 43+V(2) 3 11+V(1) <A(3) 3
6 9+3*V(1) -3+-1*V(1) [*]* 43+V(2) 3 <A(3) 32+V(1)
7 11+3*V(1) -1+-1*V(1) [*]* 43+V(2) 1 (1)A> 32+V(1)
8 13+4*V(1) 1 [*]* 43+V(2) 13+V(1) (1)A>
9 14+4*V(1) 2 [*]* 43+V(2) 14+V(1) (1)B>
10 16+4*V(1) 0 [*]* 43+V(2) 14+V(1) <A(3) 2
11 20+5*V(1) -4+-1*V(1) [*]* 43+V(2) <A(3) 34+V(1) 2
12 22+5*V(1) -2+-1*V(1) [*]* 42+V(2) 3 (1)A> 34+V(1) 2
13 26+6*V(1) 2 [*]* 42+V(2) 3 14+V(1) (1)A> 2
14 28+6*V(1) 0 [*]* 42+V(2) 3 14+V(1) <A(3) 1
15 32+7*V(1) -4+-1*V(1) [*]* 42+V(2) 3 <A(3) 34+V(1) 1
16 34+7*V(1) -2+-1*V(1) [*]* 42+V(2) 1 (1)A> 34+V(1) 1
17 38+8*V(1) 2 [*]* 42+V(2) 15+V(1) (1)A> 1
18 40+8*V(1) 0 [*]* 42+V(2) 15+V(1) <A(3) 3
19 45+9*V(1) -5+-1*V(1) [*]* 42+V(2) <A(3) 36+V(1)
20 47+9*V(1) -3+-1*V(1) [*]* 41+V(2) 3 (1)A> 36+V(1)
21 53+10*V(1) 3 [*]* 41+V(2) 3 16+V(1) (1)A>
22 54+10*V(1) 4 [*]* 41+V(2) 3 17+V(1) (1)B>
23 56+10*V(1) 2 [*]* 41+V(2) 3 17+V(1) <A(3) 2
24 63+11*V(1) -5+-1*V(1) [*]* 41+V(2) 3 <A(3) 37+V(1) 2
25 65+11*V(1) -3+-1*V(1) [*]* 41+V(2) 1 (1)A> 37+V(1) 2
26 72+12*V(1) 4 [*]* 41+V(2) 18+V(1) (1)A> 2
<< Success! ==> defined new CTR 1 (PA)
51 119 9 1 43 18 <A(3) 1
52 127 1 1 43 <A(3) 38 1
53 129 3 1 42 3 (1)A> 38 1
54 137 11 1 42 3 18 (1)A> 1
55 139 9 1 42 3 18 <A(3) 3
56 147 1 1 42 3 <A(3) 39
57 149 3 1 42 1 (1)A> 39
58 158 12 1 42 110 (1)A>
59 159 13 1 42 111 (1)B>
60 161 11 1 42 111 <A(3) 2
61 172 0 1 42 <A(3) 311 2
62 174 2 1 4 3 (1)A> 311 2
63 185 13 1 4 3 111 (1)A> 2
64 187 11 1 4 3 111 <A(3) 1
65 198 0 1 4 3 <A(3) 311 1
66 200 2 1 4 1 (1)A> 311 1
67 211 13 1 4 112 (1)A> 1
68 213 11 1 4 112 <A(3) 3
69 225 -1 1 4 <A(3) 313
70 227 1 1 3 (1)A> 313
71 240 14 1 3 113 (1)A>
72 241 15 1 3 114 (1)B>
73 243 13 1 3 114 <A(3) 2
74 257 -1 1 3 <A(3) 314 2
75 259 1 12 (1)A> 314 2
76 273 15 116 (1)A> 2
77 275 13 116 <A(3) 1
78 291 -3 <A(3) 316 1
79 293 -1 1 (4)B> 316 1
80 309 15 1 416 (4)B> 1
81 312 16 1 416 3 (1)A>
82 313 17 1 416 3 1 (1)B>
83 315 15 1 416 3 1 <A(3) 2
84 316 14 1 416 3 <A(3) 3 2
85 318 16 1 416 1 (1)A> 3 2
86 319 17 1 416 12 (1)A> 2
>> Try to prove a PPA-CTR with 2 Vars...
0 0 0 11+V(2) 43 11+V(1) (1)A> 2
1 2 -2 11+V(2) 43 11+V(1) <A(3) 1
2 3+V(1) -3+-1*V(1) 11+V(2) 43 <A(3) 31+V(1) 1
3 5+V(1) -1+-1*V(1) 11+V(2) 42 3 (1)A> 31+V(1) 1
4 6+2*V(1) 0 11+V(2) 42 3 11+V(1) (1)A> 1
5 8+2*V(1) -2 11+V(2) 42 3 11+V(1) <A(3) 3
6 9+3*V(1) -3+-1*V(1) 11+V(2) 42 3 <A(3) 32+V(1)
7 11+3*V(1) -1+-1*V(1) 11+V(2) 42 1 (1)A> 32+V(1)
8 13+4*V(1) 1 11+V(2) 42 13+V(1) (1)A>
9 14+4*V(1) 2 11+V(2) 42 14+V(1) (1)B>
10 16+4*V(1) 0 11+V(2) 42 14+V(1) <A(3) 2
11 20+5*V(1) -4+-1*V(1) 11+V(2) 42 <A(3) 34+V(1) 2
12 22+5*V(1) -2+-1*V(1) 11+V(2) 4 3 (1)A> 34+V(1) 2
13 26+6*V(1) 2 11+V(2) 4 3 14+V(1) (1)A> 2
14 28+6*V(1) 0 11+V(2) 4 3 14+V(1) <A(3) 1
15 32+7*V(1) -4+-1*V(1) 11+V(2) 4 3 <A(3) 34+V(1) 1
16 34+7*V(1) -2+-1*V(1) 11+V(2) 4 1 (1)A> 34+V(1) 1
17 38+8*V(1) 2 11+V(2) 4 15+V(1) (1)A> 1
18 40+8*V(1) 0 11+V(2) 4 15+V(1) <A(3) 3
19 45+9*V(1) -5+-1*V(1) 11+V(2) 4 <A(3) 36+V(1)
20 47+9*V(1) -3+-1*V(1) 11+V(2) 3 (1)A> 36+V(1)
21 53+10*V(1) 3 11+V(2) 3 16+V(1) (1)A>
22 54+10*V(1) 4 11+V(2) 3 17+V(1) (1)B>
23 56+10*V(1) 2 11+V(2) 3 17+V(1) <A(3) 2
24 63+11*V(1) -5+-1*V(1) 11+V(2) 3 <A(3) 37+V(1) 2
25 65+11*V(1) -3+-1*V(1) 12+V(2) (1)A> 37+V(1) 2
26 72+12*V(1) 4 19+V(1)+V(2) (1)A> 2
27 74+12*V(1) 2 19+V(1)+V(2) <A(3) 1
28 83+13*V(1)+V(2) -7+-1*V(1)+-1*V(2) <A(3) 39+V(1)+V(2) 1
29 85+13*V(1)+V(2) -5+-1*V(1)+-1*V(2) 1 (4)B> 39+V(1)+V(2) 1
30 94+14*V(1)+2*V(2) 4 1 49+V(1)+V(2) (4)B> 1
31 97+14*V(1)+2*V(2) 5 1 49+V(1)+V(2) 3 (1)A>
32 98+14*V(1)+2*V(2) 6 1 49+V(1)+V(2) 3 1 (1)B>
33 100+14*V(1)+2*V(2) 4 1 49+V(1)+V(2) 3 1 <A(3) 2
34 101+14*V(1)+2*V(2) 3 1 49+V(1)+V(2) 3 <A(3) 3 2
35 103+14*V(1)+2*V(2) 5 1 49+V(1)+V(2) 1 (1)A> 3 2
36 104+14*V(1)+2*V(2) 6 1 49+V(1)+V(2) 12 (1)A> 2
<< Success! ==> defined new CTR 2 (PPA)
86 319 17 1 416 12 (1)A> 2
== Executing PA-CTR 1, V(1)=1, V(2)=12, repcount=5, factor=7/3
216 1579 37 1 4 137 (1)A> 2
217 1581 35 1 4 137 <A(3) 1
218 1618 -2 1 4 <A(3) 337 1
219 1620 0 1 3 (1)A> 337 1
220 1657 37 1 3 137 (1)A> 1
221 1659 35 1 3 137 <A(3) 3
222 1696 -2 1 3 <A(3) 338
223 1698 0 12 (1)A> 338
224 1736 38 140 (1)A>
225 1737 39 141 (1)B>
226 1739 37 141 <A(3) 2
227 1780 -4 <A(3) 341 2
228 1782 -2 1 (4)B> 341 2
229 1823 39 1 441 (4)B> 2
230 1824 40 1 442 (3)A>
231 1825 41 1 442 3 (1)B>
232 1827 39 1 442 3 <A(3) 2
233 1829 41 1 442 1 (1)A> 2
>> Try to prove a PPA-CTR with 2 Vars...
0 0 0 11+V(2) 4 11+V(1) (1)A> 2
1 2 -2 11+V(2) 4 11+V(1) <A(3) 1
2 3+V(1) -3+-1*V(1) 11+V(2) 4 <A(3) 31+V(1) 1
3 5+V(1) -1+-1*V(1) 11+V(2) 3 (1)A> 31+V(1) 1
4 6+2*V(1) 0 11+V(2) 3 11+V(1) (1)A> 1
5 8+2*V(1) -2 11+V(2) 3 11+V(1) <A(3) 3
6 9+3*V(1) -3+-1*V(1) 11+V(2) 3 <A(3) 32+V(1)
7 11+3*V(1) -1+-1*V(1) 12+V(2) (1)A> 32+V(1)
8 13+4*V(1) 1 14+V(1)+V(2) (1)A>
9 14+4*V(1) 2 15+V(1)+V(2) (1)B>
10 16+4*V(1) 0 15+V(1)+V(2) <A(3) 2
11 21+5*V(1)+V(2) -5+-1*V(1)+-1*V(2) <A(3) 35+V(1)+V(2) 2
12 23+5*V(1)+V(2) -3+-1*V(1)+-1*V(2) 1 (4)B> 35+V(1)+V(2) 2
13 28+6*V(1)+2*V(2) 2 1 45+V(1)+V(2) (4)B> 2
14 29+6*V(1)+2*V(2) 3 1 46+V(1)+V(2) (3)A>
15 30+6*V(1)+2*V(2) 4 1 46+V(1)+V(2) 3 (1)B>
16 32+6*V(1)+2*V(2) 2 1 46+V(1)+V(2) 3 <A(3) 2
17 34+6*V(1)+2*V(2) 4 1 46+V(1)+V(2) 1 (1)A> 2
<< Success! ==> defined new CTR 3 (PPA)
233 1829 41 1 442 1 (1)A> 2
== Executing PA-CTR 1, V(1)=0, V(2)=38, repcount=13, factor=7/3
571 9317 93 1 43 192 (1)A> 2
== Executing PPA-CTR 2 (once), V(1)=91, V(2)=0
607 10695 99 1 4100 12 (1)A> 2
== Executing PA-CTR 1, V(1)=1, V(2)=96, repcount=33, factor=7/3
1465 57819 231 1 4 1233 (1)A> 2
== Executing PPA-CTR 3 (once), V(1)=232, V(2)=0
1482 59245 235 1 4238 1 (1)A> 2
== Executing PA-CTR 1, V(1)=0, V(2)=234, repcount=79, factor=7/3
3536 323737 551 1 4 1554 (1)A> 2
== Executing PPA-CTR 3 (once), V(1)=553, V(2)=0
3553 327089 555 1 4559 1 (1)A> 2
== Executing PA-CTR 1, V(1)=0, V(2)=555, repcount=186, factor=7/3
8389 1785701 1299 1 4 11303 (1)A> 2
== Executing PPA-CTR 3 (once), V(1)=1302, V(2)=0
8406 1793547 1303 1 41308 1 (1)A> 2
== Executing PA-CTR 1, V(1)=0, V(2)=1304, repcount=435, factor=7/3
19716 9754047 3043 1 43 13046 (1)A> 2
== Executing PPA-CTR 2 (once), V(1)=3045, V(2)=0
19752 9796781 3049 1 43054 12 (1)A> 2
== Executing PA-CTR 1, V(1)=1, V(2)=3050, repcount=1017, factor=7/3
46194 53279633 7117 1 43 17121 (1)A> 2
== Executing PPA-CTR 2 (once), V(1)=7120, V(2)=0
46230 53379417 7123 1 47129 12 (1)A> 2
== Executing PA-CTR 1, V(1)=1, V(2)=7125, repcount=2376, factor=7/3
108006 290585001 16627 1 4 116634 (1)A> 2
== Executing PPA-CTR 3 (once), V(1)=16633, V(2)=0
108023 290684833 16631 1 416639 1 (1)A> 2
== Executing PA-CTR 1, V(1)=0, V(2)=16635, repcount=5546, factor=7/3
252219 1582692085 38815 1 4 138823 (1)A> 2
== Executing PPA-CTR 3 (once), V(1)=38822, V(2)=0
252236 1582925051 38819 1 438828 1 (1)A> 2
== Executing PA-CTR 1, V(1)=0, V(2)=38824, repcount=12942, factor=7/3
588728 8618118599 90587 1 42 190595 (1)A> 2
588729 8618118601 90585 1 42 190595 <A(3) 1
588730 8618209196 -10 1 42 <A(3) 390595 1
588731 8618209198 -8 1 4 3 (1)A> 390595 1
588732 8618299793 90587 1 4 3 190595 (1)A> 1
588733 8618299795 90585 1 4 3 190595 <A(3) 3
588734 8618390390 -10 1 4 3 <A(3) 390596
588735 8618390392 -8 1 4 1 (1)A> 390596
588736 8618480988 90588 1 4 190597 (1)A>
588737 8618480989 90589 1 4 190598 (1)B>
588738 8618480991 90587 1 4 190598 <A(3) 2
588739 8618571589 -11 1 4 <A(3) 390598 2
588740 8618571591 -9 1 3 (1)A> 390598 2
588741 8618662189 90589 1 3 190598 (1)A> 2
588742 8618662191 90587 1 3 190598 <A(3) 1
588743 8618752789 -11 1 3 <A(3) 390598 1
588744 8618752791 -9 12 (1)A> 390598 1
588745 8618843389 90589 190600 (1)A> 1
588746 8618843391 90587 190600 <A(3) 3
588747 8618933991 -13 <A(3) 390601
588748 8618933993 -11 1 (4)B> 390601
588749 8619024594 90590 1 490601 (4)B>
588750 8619024596 90590 1 490601 (1)Z> 2 [stop]
Lines: 144
Top steps: 143
Macro steps: 588750
Basic steps: 8619024596
Tape index: 90590
nonzeros: 90604
log10(nonzeros): 4.957
log10(steps ): 9.935
Run state: stop
Input to awk program:
gohalt 1
nbs 5
T 2-state 5-symbol TM #a (G. Lafitte & C. Papazian)
5T B1R A3L B1L A1R A3R B2L A3L A3R B4R Z1R
: 90'604 8'619'024'596
L 4
M 200
pref sim
machv Laf25_a just simple
machv Laf25_a-r with repetitions reduced
machv Laf25_a-1 with tape symbol exponents
machv Laf25_a-m as 1-bck-macro machine
machv Laf25_a-a as 1-bck-macro machine with pure additive config-TRs
iam Laf25_a-a
mtype 1 0
mmtyp 3
r 1
H 1
mac 0
E 2
sympr
HM 1
date Tue Jul 6 22:11:53 CEST 2010
edate Tue Jul 6 22:11:54 CEST 2010
bnspeed 1
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:11:53 CEST 2010