GTM64 implements the same pair-rewriting algorithm as the machines described in the previous posting, now restricted to ordinals less than ω2 instead of ω2. Since every pair (i,j) (denoting ωi + j) now has i=0 or i=1, the portion of the program that copies i is thereby simplified. The machine now initialises the tape to <n><i><j> = <0><1><2>, and thus computes hωi + j(n) + 1 = hω+2(0) + 1 = hω+1(hω+1(4)) + 1 >> G, where the h-functions are as described in the previous posting.
GTM64
This machine begins by writing <n><i><j> = <0><1><2> on an initially all-0 tape, doing so by using a 3-state busy beaver with two states added to produce the required configuration (0) 10 110 1110, where parentheses again indicate the current cell. (NB: A reduction by one more state would be realised by finding a shorter way to produce a configuration of the form (0)A0{X0Y0}, where the {}-bracketed part may be repeated any number of times with possibly different Xs and Ys, and where A, X, Y are blocks of 1s with A ≥ '1', '1' ≤ X ≤ '11', Y ≥ '1', such that X0Y = 110111 occurs at least once. It seems quite possible, if not probable, that such a configuration either occurs among the halting configurations of the multitude of 4-state Busy Beaver candidates, or could be produced by adding just one state to some 3-state Busy Beaver candidate.)
Program revisions have involved deleting some states, causing gaps in the labelling sequence within certain blocks of states. Here is the "raw" GTM64 with 68 states, four of which will later be eliminated by relabelling:
rawGTM64
<n> <i> <j>
initialise tape: (0) → (0) 10 110 1110
a1 0 1 R a2
a1 1 0 L a4
a2 0 0 R a3
a2 1 1 R a2
a3 0 1 L a3
a3 1 1 L a1
a4 0 1 L b1 @ (0) 10 110 1110
a4 1 1 L a5
a5 0 0 L a4
a5 1 1 L a5
MAIN LOOP:
@(0) 1^{n+1}; increment <n> and shift right to the next 0
b1 0 1 R b2
b1 1
b2 0 0 R c1 @ 0 1^{n+2} (0)1... (if pair exists) -OR- 0 1^{n+2} (0)0... (if no pair)
b2 1 1 R b2
@(0)?; check whether a pair exists; if no pair then halt else shift to the rightmost pair <i,j>
c1 0 0 L * shift left and halt: 011...1(0)
c1 1 1 R d1 shift to, and reduce, the rightmost pair <i,j>
shift to the rightmost 00
d1 0 0 R d2
d1 1 1 R d1
d2 0 0 L e1 @<i,j>(0)0; goto reduce @<i,j>
d2 1 1 R d1
@<i,j>(0); reduce the rightmost pair <i,j>
e1 0 0 L e1
e1 1 0 L e2 dec <j>
e2 0 0 L e4 if 0: (<j> is deleted); goto dec <i>
e2 1 1 L f1 if 1: (pair is reduced); shift to leftmost 00, then multicopy <i,j>
e4 0
e4 1 0 L e5 dec <i>
e5 0 0 L g1 if 0: (pair is deleted); shift to leftmost 00, then reenter the main loop
e5 1 1 R h1 if 1: (<i> is decremented and <j> is deleted); shift to leftmost 00, copy <n> to replace the deleted <j>, then multicopy <i,j>
END MAIN LOOP
SUBROUTINES ...
shift leftward to 00, then multicopy the reduced pair
f1 0 0 L f2
f1 1 1 L f1
f2 0 0 R p1 goto multicopy the reduced pair
f2 1 1 L f1
shift leftward to 00, then reenter the main loop
g1 0 0 L g2
g1 1 1 L g1
g2 0 0 R b1 reenter the main loop
g2 1 1 L g1
shift leftward to 00, then restore deleted <j> with <n>
h1 0 0 L h2
h1 1 1 L h1
h2 0 0 R i1 goto copy <n> to replace a deleted <j>
h2 1 1 L h1
COPY<n>:
blocks i-m restore a deleted <j> on the right end by replacing it with a copy of <n>
countdown through <n> by moving the '00' rightward one place in each pass of the SUBLOOP
@ 0(0)1^{n+1};
initialise the SUBLOOP by creating a leftmost 100 and by appending a rightmost 011
change 00<n> to 100<n>: 0(0)11..10 → 100(1)1...10
i1 0 0 L i2
i1 1
i2 0 1 R i3
i2 1
i3 0 0 R i3
i3 1 0 R j1 @100(1)1...10
shift to rightmost 00 and append an initial 011 to the unpaired <i>
j1 0 0 R j2
j1 1 1 R j1
j2 0 1 R j4
j2 1 1 R j1
j4 0 1 L k1 @<i>0(1)1
j4 1
COPY<n> SUBLOOP:
shift leftward to the 00 in the countdown
k1 0 0 L k2
k1 1 1 L k1
k2 0 0 R l1 @10(0)1
k2 1 1 L k1
change the 1001 to 1100 and test 1100(?)
l1 0 0 L l2
l1 1
l2 0 1 R l3
l2 1
l3 0 0 R l3
l3 1 0 R l4 @1100(?)
l4 0 0 L l6 if 0: (done copying <n>); restore <n> as <n+3>, shift to the leftmost 00 and goto multicopy the reduced pair
l4 1 1 L m1 if 1: append 1 to the partial copy of <n>
restore <n> as <n+3>
l6 0 1 L l6
l6 1 1 L l7
l7 0 1 L p1 @ leftmost 0(0); goto multicopy the reduced pair
l7 1 1 L l7
shift to the rightmost 00 and append 1 to the partial copy of <n>
m1 0 0 R m2
m1 1 1 R m1
m2 0 0 L m4
m2 1 1 R m1
m4 0 1 L k1 loop back to append another 1 or finish
m4 1
END COPY<n> SUBLOOP
END COPY<n>
MULTICOPY<i,j> LOOP:
@ leftmost 0(0); multicopy (n times) the reduced pair <i,j>
countdown through <n> by moving the '00' rightward one place in each pass of MULTICOPY<i,j> LOOP
change 00<n> to 100<n>: 0(0)11..10 → 100(1)1...10
p1 0 0 L p2
p1 1
p2 0 1 R p3
p2 1
p3 0 0 R p3
p3 1 0 R p4 @100(?)
p4 0 0 L p6 if 0: (done multicopying); restore <n> & reenter main loop
p4 1 1 L q1 if 1: (continue with multicopy); copy the rightmost pair <i,j>
restore <n> & reenter main loop
p6 0 1 L p6
p6 1 1 L p7
p7 0 1 L b1 @ leftmost 0(0); reenter the main loop
p7 1 1 L p7
initialise copying of <i>: <j>0(0) → <j>0(1)
shift to rightmost 00 and change it to 01
q1 0 0 R q2
q1 1 1 R q1
q2 0 1 L q4
q2 1 1 R q1
shift to the leftmost 1 in <i>
q4 0 0 L q5
q4 1
q5 0 0 L q6
q5 1 1 L q5 pass over <j>
q6 0 0 R q7
q6 1 1 L q6
COPY<i> (not a loop):
@leftmost 1 in <i>
q7 0
q7 1 1 R q8 @1(?)
q8 0 0 L v1 if 0: (i=0)(done copying <i>); initialise & copy <j>
q8 1 1 L s1 if 1: (i=1); append 1 to the partial copy of <i>
shift rightward to 00 and change it to 10
s1 0 0 R s2
s1 1 1 R s1
s2 0 0 L s4
s2 1 1 R s1
s4 0 1 L v1 (done copying i=1); begin copying <j>
s4 1
END COPY<i>
initialise copying of <j>: <i><j><i>0(0) → <i><j><i>0(1);
then shift to the leftmost 1 in <j>
v1 0 0 R v2
v1 1 1 R v1
v2 0 1 L v4
v2 1 1 R v1
v4 0 0 L v5 shift to leftmost 1 in <j>
v4 1
v5 0 0 L v6
v5 1 1 L v5 pass over the copy of <i>
v6 0 0 R v7 @leftmost 1 in <j>; enter the copy <j> subloop
v6 1 1 L v6
COPY<j> SUBLOOP:
@leftmost 1 in <j>
countdown through <j> by changing 01^{j+1} to 001^{j} in each pass of COPY<j> SUBLOOP until 000 is produced
v7 0
v7 1 0 R v8 @00(?)
v8 0 0 L z1 if 0: restore <j>, then shift to the leftmost 00 and continue the multicopying loop
v8 1 1 R x1 if 1: append 1 to the partial copy of <j>
shift right to 00 and change it to 10
x1 0 0 R x2
x1 1 1 R x1
x2 0 0 L x4
x2 1 1 R x1
x4 0 1 L y1 goto shift back to the leftmost 1 in <j>
x4 1
shift left to the leftmost 1 in <j>
y1 0 0 L y2
y1 1 1 L y1
y2 0 0 L y3
y2 1 1 L y2
y3 0 0 R v7 @leftmost 1 in <j>; loop back to continue the COPY<j> SUBLOOP
y3 1 1 L y3
END COPY<j> SUBLOOP
z1 0 1 L z1 restore the 1s in <j> (overwrites the initial 0 in <j>)
z1 1 1 R z2 goto restore the initial 0 in <j>
z2 0
z2 1 0 R f1 restore the initial 0 in <j>; (done with copy<j>); shift to the leftmost 00 and loop back to continue MULTICOPY<i,j>
END MULTICOPY<i,j> LOOP
END rawGTM64
Reclaiming unused "half-states"
In the machine rawGTM64, each of the four states (e4, q7, v7, z2) is only "half used", and they can be eliminated by relabelling them as the previously "unused halves" of the four states (b1, q4, v4, x4):
e4 1 0 L e5 → b1 1 0 L e5 q7 1 1 R q8 → q4 1 1 R q8 v7 1 0 R v8 → v4 1 0 R v8 z2 1 0 R f1 → x4 1 0 R f1This yields a 64-state machine in which there remain nine unused half-states (i1 1, i2 1, j4 1, l1 1, l2 1, m4 1, p1 1, p2 1, and s4 1). Here is the transition table as a Python list of numerical tuples with the states labelled consecutively 1-64, with Halt labelled as 0, and with L/R coded as 0/1 (the unused half-states are omitted):
GTM64 = \ [ (1,0,1,1,2), (1,1,0,0,4), (2,0,0,1,3), (2,1,1,1,2), (3,0,1,0,3), (3,1,1,0,1), (4,0,1,0,6), (4,1,1,0,5), (5,0,0,0,4), (5,1,1,0,5), (6,0,1,1,7), (6,1,0,0,13), (7,0,0,1,8), (7,1,1,1,7), (8,0,0,0,0), (8,1,1,1,9), (9,0,0,1,10), (9,1,1,1,9), (10,0,0,0,11), (10,1,1,1,9), (11,0,0,0,11), (11,1,0,0,12), (12,0,0,0,6), (12,1,1,0,14), (13,0,0,0,16), (13,1,1,1,18), (14,0,0,0,15), (14,1,1,0,14), (15,0,0,1,37), (15,1,1,0,14), (16,0,0,0,17), (16,1,1,0,16), (17,0,0,1,6), (17,1,1,0,16), (18,0,0,0,19), (18,1,1,0,18), (19,0,0,1,20), (19,1,1,0,18), (20,0,0,0,21), (21,0,1,1,22), (22,0,0,1,22), (22,1,0,1,23), (23,0,0,1,24), (23,1,1,1,23), (24,0,1,1,25), (24,1,1,1,23), (25,0,1,0,26), (26,0,0,0,27), (26,1,1,0,26), (27,0,0,1,28), (27,1,1,0,26), (28,0,0,0,29), (29,0,1,1,30), (30,0,0,1,30), (30,1,0,1,31), (31,0,0,0,32), (31,1,1,0,34), (32,0,1,0,32), (32,1,1,0,33), (33,0,1,0,37), (33,1,1,0,33), (34,0,0,1,35), (34,1,1,1,34), (35,0,0,0,36), (35,1,1,1,34), (36,0,1,0,26), (37,0,0,0,38), (38,0,1,1,39), (39,0,0,1,39), (39,1,0,1,40), (40,0,0,0,41), (40,1,1,0,43), (41,0,1,0,41), (41,1,1,0,42), (42,0,1,0,6), (42,1,1,0,42), (43,0,0,1,44), (43,1,1,1,43), (44,0,1,0,45), (44,1,1,1,43), (45,0,0,0,46), (45,1,1,1,48), (46,0,0,0,47), (46,1,1,0,46), (47,0,0,1,45), (47,1,1,0,47), (48,0,0,0,52), (48,1,1,0,49), (49,0,0,1,50), (49,1,1,1,49), (50,0,0,0,51), (50,1,1,1,49), (51,0,1,0,52), (52,0,0,1,53), (52,1,1,1,52), (53,0,1,0,54), (53,1,1,1,52), (54,0,0,0,55), (54,1,0,1,57), (55,0,0,0,56), (55,1,1,0,55), (56,0,0,1,54), (56,1,1,0,56), (57,0,0,0,64), (57,1,1,1,58), (58,0,0,1,59), (58,1,1,1,58), (59,0,0,0,60), (59,1,1,1,58), (60,0,1,0,61), (60,1,0,1,14), (61,0,0,0,62), (61,1,1,0,61), (62,0,0,0,63), (62,1,1,0,62), (63,0,0,1,54), (63,1,1,0,63), (64,0,1,0,64), (64,1,1,1,60) ]
No comments:
Post a Comment