Comment: This TM produces 1,137,477 nonzeros in 924,180,005,181 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 | A3R | A1L | B1L | B3L | 1 | right | B | 3 | right | A | 1 | left | A | 1 | left | B | 3 | left | B |
| B | A2L | B4L | A3R | B2R | Z1R | 2 | left | A | 4 | left | B | 3 | right | A | 2 | 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 bck-macro machine.
Simulation is done as bck-macro machine with pure additive config-TRs.
Pushing initial machine.
Pushing BCK machine.
Steps BasSteps BasTpos Tape contents
0 0 0 (0)A>
1 1 1 (1)B>
2 5 -1 <B(1) 1
3 6 -2 <A(2) 12
4 8 0 1 (3)A> 12
5 10 2 1 32 (3)A>
6 11 3 1 33 (1)B>
7 15 1 1 33 <B(1) 1
8 21 3 1 32 2 (2)B> 1
9 26 4 1 32 22 (2)B>
10 28 2 1 32 22 <A(1) 2
11 30 0 1 32 <A(1) 12 2
12 31 -1 1 3 <B(1) 13 2
13 37 1 1 2 (2)B> 13 2
14 52 4 1 24 (2)B> 2
15 53 5 1 25 (3)A>
16 54 6 1 25 3 (1)B>
17 58 4 1 25 3 <B(1) 1
18 64 6 1 26 (2)B> 1
19 69 7 1 27 (2)B>
20 71 5 1 27 <A(1) 2
21 78 -2 1 <A(1) 17 2
22 80 0 3 (3)A> 17 2
23 87 7 38 (3)A> 2
24 89 5 38 <B(1) 1
25 95 7 37 2 (2)B> 1
26 100 8 37 22 (2)B>
27 102 6 37 22 <A(1) 2
28 104 4 37 <A(1) 12 2
29 105 3 36 <B(1) 13 2
30 111 5 35 2 (2)B> 13 2
31 126 8 35 24 (2)B> 2
32 127 9 35 25 (3)A>
33 128 10 35 25 3 (1)B>
34 132 8 35 25 3 <B(1) 1
35 138 10 35 26 (2)B> 1
>> Try to prove a PA-CTR with 2 Vars...
0 0 0 33+V(2) 21+V(1) (2)B> 1
1 5 1 33+V(2) 22+V(1) (2)B>
2 7 -1 33+V(2) 22+V(1) <A(1) 2
3 9+V(1) -3+-1*V(1) 33+V(2) <A(1) 12+V(1) 2
4 10+V(1) -4+-1*V(1) 32+V(2) <B(1) 13+V(1) 2
5 16+V(1) -2+-1*V(1) 31+V(2) 2 (2)B> 13+V(1) 2
6 31+6*V(1) 1 31+V(2) 24+V(1) (2)B> 2
7 32+6*V(1) 2 31+V(2) 25+V(1) (3)A>
8 33+6*V(1) 3 31+V(2) 25+V(1) 3 (1)B>
9 37+6*V(1) 1 31+V(2) 25+V(1) 3 <B(1) 1
10 43+6*V(1) 3 31+V(2) 26+V(1) (2)B> 1
<< Success! ==> defined new CTR 1 (PA)
35 138 10 35 26 (2)B> 1
== Executing PA-CTR 1, V(1)=5, V(2)=2, repcount=2, factor=5/2
55 314 16 3 216 (2)B> 1
56 319 17 3 217 (2)B>
57 321 15 3 217 <A(1) 2
58 338 -2 3 <A(1) 117 2
59 339 -3 <B(1) 118 2
60 340 -4 <A(2) 119 2
61 342 -2 1 (3)A> 119 2
62 361 17 1 319 (3)A> 2
63 363 15 1 319 <B(1) 1
64 369 17 1 318 2 (2)B> 1
65 374 18 1 318 22 (2)B>
66 376 16 1 318 22 <A(1) 2
67 378 14 1 318 <A(1) 12 2
68 379 13 1 317 <B(1) 13 2
69 385 15 1 316 2 (2)B> 13 2
70 400 18 1 316 24 (2)B> 2
71 401 19 1 316 25 (3)A>
72 402 20 1 316 25 3 (1)B>
73 406 18 1 316 25 3 <B(1) 1
74 412 20 1 316 26 (2)B> 1
>> Try to prove a PA-CTR with 2 Vars...
0 0 0 [*]* 33+V(2) 21+V(1) (2)B> 1
1 5 1 [*]* 33+V(2) 22+V(1) (2)B>
2 7 -1 [*]* 33+V(2) 22+V(1) <A(1) 2
3 9+V(1) -3+-1*V(1) [*]* 33+V(2) <A(1) 12+V(1) 2
4 10+V(1) -4+-1*V(1) [*]* 32+V(2) <B(1) 13+V(1) 2
5 16+V(1) -2+-1*V(1) [*]* 31+V(2) 2 (2)B> 13+V(1) 2
6 31+6*V(1) 1 [*]* 31+V(2) 24+V(1) (2)B> 2
7 32+6*V(1) 2 [*]* 31+V(2) 25+V(1) (3)A>
8 33+6*V(1) 3 [*]* 31+V(2) 25+V(1) 3 (1)B>
9 37+6*V(1) 1 [*]* 31+V(2) 25+V(1) 3 <B(1) 1
10 43+6*V(1) 3 [*]* 31+V(2) 26+V(1) (2)B> 1
<< Success! ==> defined new CTR 2 (PA)
74 412 20 1 316 26 (2)B> 1
== Executing PA-CTR 2, V(1)=5, V(2)=13, repcount=7, factor=5/2
144 1553 41 1 32 241 (2)B> 1
145 1558 42 1 32 242 (2)B>
146 1560 40 1 32 242 <A(1) 2
147 1602 -2 1 32 <A(1) 142 2
148 1603 -3 1 3 <B(1) 143 2
149 1609 -1 1 2 (2)B> 143 2
150 1824 42 1 244 (2)B> 2
151 1825 43 1 245 (3)A>
152 1826 44 1 245 3 (1)B>
153 1830 42 1 245 3 <B(1) 1
154 1836 44 1 246 (2)B> 1
155 1841 45 1 247 (2)B>
156 1843 43 1 247 <A(1) 2
157 1890 -4 1 <A(1) 147 2
158 1892 -2 3 (3)A> 147 2
159 1939 45 348 (3)A> 2
160 1941 43 348 <B(1) 1
161 1947 45 347 2 (2)B> 1
>> Try to prove a PPA-CTR with 2 Vars...
0 0 0 1 32 21+V(1) (2)B> 11+V(2)
1 5+5*V(2) 1+V(2) 1 32 22+V(1)+V(2) (2)B>
2 7+5*V(2) -1+V(2) 1 32 22+V(1)+V(2) <A(1) 2
3 9+V(1)+6*V(2) -3+-1*V(1) 1 32 <A(1) 12+V(1)+V(2) 2
4 10+V(1)+6*V(2) -4+-1*V(1) 1 3 <B(1) 13+V(1)+V(2) 2
5 16+V(1)+6*V(2) -2+-1*V(1) 1 2 (2)B> 13+V(1)+V(2) 2
6 31+6*V(1)+11*V(2) 1+V(2) 1 24+V(1)+V(2) (2)B> 2
7 32+6*V(1)+11*V(2) 2+V(2) 1 25+V(1)+V(2) (3)A>
8 33+6*V(1)+11*V(2) 3+V(2) 1 25+V(1)+V(2) 3 (1)B>
9 37+6*V(1)+11*V(2) 1+V(2) 1 25+V(1)+V(2) 3 <B(1) 1
10 43+6*V(1)+11*V(2) 3+V(2) 1 26+V(1)+V(2) (2)B> 1
11 48+6*V(1)+11*V(2) 4+V(2) 1 27+V(1)+V(2) (2)B>
12 50+6*V(1)+11*V(2) 2+V(2) 1 27+V(1)+V(2) <A(1) 2
13 57+7*V(1)+12*V(2) -5+-1*V(1) 1 <A(1) 17+V(1)+V(2) 2
14 59+7*V(1)+12*V(2) -3+-1*V(1) 3 (3)A> 17+V(1)+V(2) 2
15 66+8*V(1)+13*V(2) 4+V(2) 38+V(1)+V(2) (3)A> 2
16 68+8*V(1)+13*V(2) 2+V(2) 38+V(1)+V(2) <B(1) 1
17 74+8*V(1)+13*V(2) 4+V(2) 37+V(1)+V(2) 2 (2)B> 1
<< Success! ==> defined new CTR 3 (PPA)
161 1947 45 347 2 (2)B> 1
== Executing PA-CTR 1, V(1)=0, V(2)=44, repcount=23, factor=5/2
391 10526 114 3 2116 (2)B> 1
392 10531 115 3 2117 (2)B>
393 10533 113 3 2117 <A(1) 2
394 10650 -4 3 <A(1) 1117 2
395 10651 -5 <B(1) 1118 2
396 10652 -6 <A(2) 1119 2
397 10654 -4 1 (3)A> 1119 2
398 10773 115 1 3119 (3)A> 2
399 10775 113 1 3119 <B(1) 1
400 10781 115 1 3118 2 (2)B> 1
>> Try to prove a PPA-CTR with 2 Vars...
0 0 0 3 21+V(1) (2)B> 11+V(2)
1 5+5*V(2) 1+V(2) 3 22+V(1)+V(2) (2)B>
2 7+5*V(2) -1+V(2) 3 22+V(1)+V(2) <A(1) 2
3 9+V(1)+6*V(2) -3+-1*V(1) 3 <A(1) 12+V(1)+V(2) 2
4 10+V(1)+6*V(2) -4+-1*V(1) <B(1) 13+V(1)+V(2) 2
5 11+V(1)+6*V(2) -5+-1*V(1) <A(2) 14+V(1)+V(2) 2
6 13+V(1)+6*V(2) -3+-1*V(1) 1 (3)A> 14+V(1)+V(2) 2
7 17+2*V(1)+7*V(2) 1+V(2) 1 34+V(1)+V(2) (3)A> 2
8 19+2*V(1)+7*V(2) -1+V(2) 1 34+V(1)+V(2) <B(1) 1
9 25+2*V(1)+7*V(2) 1+V(2) 1 33+V(1)+V(2) 2 (2)B> 1
<< Success! ==> defined new CTR 4 (PPA)
400 10781 115 1 3118 2 (2)B> 1
== Executing PA-CTR 2, V(1)=0, V(2)=115, repcount=58, factor=5/2
980 62865 289 1 32 2291 (2)B> 1
== Executing PPA-CTR 3 (once), V(1)=290, V(2)=0
997 65259 293 3297 2 (2)B> 1
== Executing PA-CTR 1, V(1)=0, V(2)=294, repcount=148, factor=5/2
2477 397963 737 3 2741 (2)B> 1
== Executing PPA-CTR 4 (once), V(1)=740, V(2)=0
2486 399468 738 1 3743 2 (2)B> 1
== Executing PA-CTR 2, V(1)=0, V(2)=740, repcount=371, factor=5/2
6196 2474471 1851 1 3 21856 (2)B> 1
6197 2474476 1852 1 3 21857 (2)B>
6198 2474478 1850 1 3 21857 <A(1) 2
6199 2476335 -7 1 3 <A(1) 11857 2
6200 2476336 -8 1 <B(1) 11858 2
6201 2476337 -9 <B(4) 11859 2
6202 2476338 -10 <A(2) 4 11859 2
6203 2476340 -8 1 (3)A> 4 11859 2
6204 2476343 -7 1 2 (2)B> 11859 2
6205 2485638 1852 1 21860 (2)B> 2
6206 2485639 1853 1 21861 (3)A>
6207 2485640 1854 1 21861 3 (1)B>
6208 2485644 1852 1 21861 3 <B(1) 1
6209 2485650 1854 1 21862 (2)B> 1
6210 2485655 1855 1 21863 (2)B>
6211 2485657 1853 1 21863 <A(1) 2
6212 2487520 -10 1 <A(1) 11863 2
6213 2487522 -8 3 (3)A> 11863 2
6214 2489385 1855 31864 (3)A> 2
6215 2489387 1853 31864 <B(1) 1
6216 2489393 1855 31863 2 (2)B> 1
>> Try to prove a PPA-CTR with 2 Vars...
0 0 0 1 3 21+V(1) (2)B> 11+V(2)
1 5+5*V(2) 1+V(2) 1 3 22+V(1)+V(2) (2)B>
2 7+5*V(2) -1+V(2) 1 3 22+V(1)+V(2) <A(1) 2
3 9+V(1)+6*V(2) -3+-1*V(1) 1 3 <A(1) 12+V(1)+V(2) 2
4 10+V(1)+6*V(2) -4+-1*V(1) 1 <B(1) 13+V(1)+V(2) 2
5 11+V(1)+6*V(2) -5+-1*V(1) <B(4) 14+V(1)+V(2) 2
6 12+V(1)+6*V(2) -6+-1*V(1) <A(2) 4 14+V(1)+V(2) 2
7 14+V(1)+6*V(2) -4+-1*V(1) 1 (3)A> 4 14+V(1)+V(2) 2
8 17+V(1)+6*V(2) -3+-1*V(1) 1 2 (2)B> 14+V(1)+V(2) 2
9 37+6*V(1)+11*V(2) 1+V(2) 1 25+V(1)+V(2) (2)B> 2
10 38+6*V(1)+11*V(2) 2+V(2) 1 26+V(1)+V(2) (3)A>
11 39+6*V(1)+11*V(2) 3+V(2) 1 26+V(1)+V(2) 3 (1)B>
12 43+6*V(1)+11*V(2) 1+V(2) 1 26+V(1)+V(2) 3 <B(1) 1
13 49+6*V(1)+11*V(2) 3+V(2) 1 27+V(1)+V(2) (2)B> 1
14 54+6*V(1)+11*V(2) 4+V(2) 1 28+V(1)+V(2) (2)B>
15 56+6*V(1)+11*V(2) 2+V(2) 1 28+V(1)+V(2) <A(1) 2
16 64+7*V(1)+12*V(2) -6+-1*V(1) 1 <A(1) 18+V(1)+V(2) 2
17 66+7*V(1)+12*V(2) -4+-1*V(1) 3 (3)A> 18+V(1)+V(2) 2
18 74+8*V(1)+13*V(2) 4+V(2) 39+V(1)+V(2) (3)A> 2
19 76+8*V(1)+13*V(2) 2+V(2) 39+V(1)+V(2) <B(1) 1
20 82+8*V(1)+13*V(2) 4+V(2) 38+V(1)+V(2) 2 (2)B> 1
<< Success! ==> defined new CTR 5 (PPA)
6216 2489393 1855 31863 2 (2)B> 1
== Executing PA-CTR 1, V(1)=0, V(2)=1860, repcount=931, factor=5/2
15526 15516876 4648 3 24656 (2)B> 1
== Executing PPA-CTR 4 (once), V(1)=4655, V(2)=0
15535 15526211 4649 1 34658 2 (2)B> 1
== Executing PA-CTR 2, V(1)=0, V(2)=4655, repcount=2328, factor=5/2
38815 96885155 11633 1 32 211641 (2)B> 1
== Executing PPA-CTR 3 (once), V(1)=11640, V(2)=0
38832 96978349 11637 311647 2 (2)B> 1
== Executing PA-CTR 1, V(1)=0, V(2)=11644, repcount=5823, factor=5/2
97062 605751328 29106 3 229116 (2)B> 1
== Executing PPA-CTR 4 (once), V(1)=29115, V(2)=0
97071 605809583 29107 1 329118 2 (2)B> 1
== Executing PA-CTR 2, V(1)=0, V(2)=29115, repcount=14558, factor=5/2
242651 3785247667 72781 1 32 272791 (2)B> 1
== Executing PPA-CTR 3 (once), V(1)=72790, V(2)=0
242668 3785830061 72785 372797 2 (2)B> 1
== Executing PA-CTR 1, V(1)=0, V(2)=72794, repcount=36398, factor=5/2
606648 23659065265 181979 3 2181991 (2)B> 1
== Executing PPA-CTR 4 (once), V(1)=181990, V(2)=0
606657 23659429270 181980 1 3181993 2 (2)B> 1
== Executing PA-CTR 2, V(1)=0, V(2)=181990, repcount=90996, factor=5/2
1516617 147866057398 454968 1 3 2454981 (2)B> 1
== Executing PPA-CTR 5 (once), V(1)=454980, V(2)=0
1516637 147869697320 454972 3454988 2 (2)B> 1
== Executing PA-CTR 1, V(1)=0, V(2)=454985, repcount=227493, factor=5/2
3791567 924172042859 1137451 32 21137466 (2)B> 1
3791568 924172042864 1137452 32 21137467 (2)B>
3791569 924172042866 1137450 32 21137467 <A(1) 2
3791570 924173180333 -17 32 <A(1) 11137467 2
3791571 924173180334 -18 3 <B(1) 11137468 2
3791572 924173180340 -16 2 (2)B> 11137468 2
3791573 924178867680 1137452 21137469 (2)B> 2
3791574 924178867681 1137453 21137470 (3)A>
3791575 924178867682 1137454 21137470 3 (1)B>
3791576 924178867686 1137452 21137470 3 <B(1) 1
3791577 924178867692 1137454 21137471 (2)B> 1
3791578 924178867697 1137455 21137472 (2)B>
3791579 924178867699 1137453 21137472 <A(1) 2
3791580 924180005171 -19 <A(1) 11137472 2
3791581 924180005174 -20 <B(4) 4 11137472 2
3791582 924180005175 -21 <A(2) 42 11137472 2
3791583 924180005177 -19 1 (3)A> 42 11137472 2
3791584 924180005180 -18 1 2 (2)B> 4 11137472 2
3791585 924180005181 -17 1 22 (1)Z> 11137472 2
3791585 924180005181 -17 1 22 (1)Z> 11137472 2 [stop]
Lines: 141
Top steps: 139
Macro steps: 3791585
Basic steps: 924180005181
Tape index: -17
nonzeros: 1137477
log10(nonzeros): 6.056
log10(steps ): 11.966
Run state: stop
Input to awk program:
gohalt 1
nbs 5
T 2-state 5-symbol TM #g (G. Lafitte & C. Papazian)
5T B1R A3R A1L B1L B3L A2L B4L A3R B2R Z1R
: 1,137,477 924,180,005,181
L 4
M 201
pref sim
machv Laf25_g just simple
machv Laf25_g-r with repetitions reduced
machv Laf25_g-1 with tape symbol exponents
machv Laf25_g-m as bck-macro machine
machv Laf25_g-a as bck-macro machine with pure additive config-TRs
iam Laf25_g-a
mtype 0
mmtyp 3
r 1
H 1
mac 0
E 2
sympr
HM 1
date Tue Jul 6 22:12:04 CEST 2010
edate Tue Jul 6 22:12:04 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:12:04 CEST 2010