**64**-state 2-symbol Turing machine (GTM64) that computes a number greater than Graham's number (G), starting with a blank tape.

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