Sunday, September 19, 2010

A 64-state Turing machine whose output exceeds Graham's number

This posting describes a 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 f1
This 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)
]

Thursday, September 9, 2010

A "small" Turing machine whose output exceeds Graham's number

Revised 9/13/2010

The page "Beating Graham's number" by S. Ligocki raises two questions concerning the Busy Beaver function Σ() and Graham's number G:

(1) What is the least n such that Σ(n) > G?
(2) What is the least n for which it has been proved that Σ(n) > G?

The answer to (1) is not known, but—and this is pure speculation—it might be as small as 12 or so.

This posting answers (2) with n = 72, assuming the behavior of the machine described here (GTM72) has been adequately established. (This machine incorporates optimisations suggested by S. Ligocki in the comments section below.)


A rewriting algorithm for a fast-growing hierarchy

Consider the following "accelerated" fast-growing hierarchy:
 gα(n) 
 = n+1      if α = 0
 = (gα-1)n+1(n+1)      if α is a successor
 = (gα[n+1])n+1(n+1)      if α is a limit
where α is any ordinal in an initial segment of ordinals for which fundamental sequences have been assigned to the limit ordinals, and α[n] is the nth element of the fundamental sequence for limit α. Here (gα...)n+1 denotes the (n+1)-fold iteration of the bracketed function.

This function-hierarchy is simulated by the following rewriting system for finite sequences of ordinals prefixed by a natural number n:
 n α1 ... αk α 
 → {n+1} α1 ... αk     if α = 0
 → {n+1} α1 ... αk {α-1}n+1     if α is a successor
 → {n+1} α1 ... αk {α[n+1]}n+1      if α is a limit
where {α...}n+1 denotes a sequence of n+1 copies of the bracketed ordinal.

That is, starting with "n α" and applying the above rules repeatedly, the rewriting eventually terminates with only the natural number gα(n) remaining.

Now, every ordinal α in the range [0, ω2) has a unique representation as an ordered pair (i,j) of natural numbers denoting ω·i + j; therefore, by restricting to this initial segment of ordinals, the system can be reformulated as a rewriting system for sequences of such pairs:
 n (i1,j1) ... (ik,jk) (i,j)  
 →  {n+1} (i1,j1) ... (ik,jk)      if i = j = 0
 →  {n+1} (i1,j1) ... (ik,jk)(i,j-1)n+1      if j > 0
 →  {n+1} (i1,j1) ... (ik,jk) (i-1,n+1)n+1      if i > 0, j = 0
where (.,.)n+1 denotes a sequence of n+1 copies of the bracketed pair.

Starting with "n (i,j)", the system will thus compute gωi+j(n).

Consequently, a "Busy Beaver"-class Turing machine that halts with more than Graham's number of 1s on the tape needs only to simulate this pair-rewriting system after initialising the tape to represent relatively small values of n, i, j; e.g., starting with "n (i,j)" = "0 (2,1)", the system will compute gω2+1(0) >> G.

Because of attempting to maximise the output while minimising the number of states, the function-hierarchy actually simulated by the Turing machine described below is hα() + 1, where
 hα(n) 
 = n+1      if α = 0
 = (hα-1)n+2(n+4)      if α is a successor
 = (hα[n+1])n+5(n+7)      if α is a limit.
This particular machine initialises the tape to <0><2><1> (in unary), then computes hω2+1(0) + 1 >> fω2(fω2(6)) >> G, where fω2 is in the standard fast-growing hierarchy.


A machine that simulates the rewriting algorithm

The machine we construct uses a two-symbol tape alphabet {0,1}, in which 0 is the blank symbol and natural numbers are coded in unary; i.e., a number x is coded as <x> = 1x+10. The machine begins by writing <n><i><j> = <0><2><1> = "10 1110 110" on an initially all-0 tape, which it does by incorporating a modified 3-state busy beaver.

In the following, "home" refers to the configuration 0(0)1, where parentheses identify the current bit, and the 00 is the rightmost 00 located to the left of a current 1-bit.

Navigation through the data string is often accomplished by positioning on a 1 and then moving in a given direction until 00 is detected (e.g., the 00s that bracket the entire data string). This allows navigation to either end of the string, and also gives a method for counting through a block of 1s by progressively moving a 00 rightward through the block until 000 is produced.

The "raw" TM has 77 states, five of which will later be eliminated by combining ten unused "half states".

Here is a commented version in standard 5-tuple form:
BEGIN GTM77 
                           <n>  <i>  <j>
 initialise tape: (0) → (0) 1 0 111 0 11 0
 a1 0 1 L a2
 a1 1 0 L a4
 a2 0 0 L a3
 a2 1 1 L a2
 a3 0 1 R a3
 a3 1 1 R a1
 a4 0 0 L a5
 a4 1 1 L a4
 a5 0 1 L b1   @home(0)
 a5 1
 
 BEGIN MAIN LOOP
 
 @home(0); increment <n> and move right to the next 0 
 b1 0 1 R b2
 b1 1
 b2 0 0 R c1   00 1^{n+2} (0) 1^{i+1} 0 1^{j+1} 0 
 b2 1 1 R b2
 
 @(0); check whether a pair exists; if not then halt else move to the rightmost pair <i,j>
 c1 0 0 L *
 c1 1 1 L c2
 c2 0 0 L c2
 c2 1 1 L d1   @(1)
 
 @(1); move to the rightmost 00 
 d1 0 0 R d2 
 d1 1 1 R d1
 d2 0 0 L e1   @1(0)0
 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); go home, multicopy <i,j>
 e4 0 
 e4 1 0 L e5   dec <i>
 e5 0 0 L g1   if 0: (pair is deleted); go home, increment <n>
 e5 1 1 R e6   if 1: (<i> is decremented and <j> is deleted); go home, restore <j> with <n>, multicopy <i,j> 
 e6 0 0 L h1
 e6 1
 
 END MAIN LOOP
 
 SUBROUTINES ...
 
 @(1); go home, goto multicopy the reduced pair 
 f1 0 0 L f2
 f1 1 1 L f1
 f2 0 0 R p1   @home; goto multicopy the reduced pair
 f2 1 1 L f1
 
 @(1); go home, goto next increment <n> 
 g1 0 0 L g2
 g1 1 1 L g1
 g2 0 0 R b1   @home; goto next increment <n>
 g2 1 1 L g1
 
 @(1); go home, goto restore <j> with <n> 
 h1 0 0 L h2
 h1 1 1 L h1
 h2 0 0 R i1   @home; goto restore <j> with <n>
 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>
 
 @home(0)11..10; count through <n> by moving a '00' rightward one place in each pass
 
 begin by changing 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
 
 @(1); 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
 
 BEGIN COPY<n> SUBLOOP
 
 @(1) in partial <j>; move to the leftmost 1001
 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; restore <n> as <n+3>, go home, goto multicopy the reduced pair
 l4 1 1 L l5  if 1: append 1 to the partial copy of <n> 
 l5 0 0 R m1
 l5 1 
 l6 0 1 L l6  
 l6 1 1 L l7
 l7 0 1 L p1  @home(0); goto multicopy the reduced pair
 l7 1 1 L l7 
 
 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  @(1) in partial <j>; loop back to append another 1 or finish
 m4 1
 
 END COPY<n> SUBLOOP 
 
 MULTICOPY<i,j>
 
 @home(0); multicopy (n times) the reduced pair <i,j> 
 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 p5  if 1: (continue with multicopy); copy the rightmost pair <i,j>
 p5 0 0 R q1  @(1); move to <j>0(0)
 p5 1
 p6 0 1 L p6
 p6 1 1 L p7
 p7 0 1 L b1  @home(0); goto next increment <n>
 p7 1 1 L p7 
 
 @(1); initialise copying of <i>:  <j>0(0) → <j>0(1)  
 q1 0 0 R q2
 q1 1 1 R q1
 q2 0 1 L q4
 q2 1 1 R q1
 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 
 
 BEGIN COPY<i> SUBLOOP 
 
 @leftmost 1 in <i>
 q7 0 
 q7 1 0 R q8  @00(?)
 q8 0 0 L u1  if 0: restore <i>, initialise & copy <j>
 q8 1 1 R s1  if 1: append 1 to the partial copy of <i> 
 
 s1 0 0 R s2
 s1 1 1 R s1
 s2 0 0 L s4  
 s2 1 1 R s1 
 s4 0 1 L t1
 s4 1 
 
 t1 0 0 L t2
 t1 1 1 L t1
 t2 0 0 L t3
 t2 1 1 L t2
 t3 0 0 R q7  @leftmost 1 in <i>
 t3 1 1 L t3
 
 u1 0 1 L u1
 u1 1 1 R u2
 u2 0 
 u2 1 0 R v1 @(1) in <i> (done with copy<i>); proceed to copy <j>
 
 END COPY<i> SUBLOOP
 
 (blocks v-z essentially duplicate blocks q-u)
 
 @(1); initialise copying of <j>: <i><j><i>0(0) → <i><j><i>0(1)  
 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
 v4 1
 v5 0 0 L v6
 v5 1 1 L v5  pass over <i>
 v6 0 0 R v7
 v6 1 1 L v6 
 
 BEGIN COPY<j> SUBLOOP
 
 @leftmost 1 in <j>
 v7 0           
 v7 1 0 R v8  @00(?)
 v8 0 0 L z1  if 0: restore <j>, go home and continue the multicopying loop
 v8 1 1 R x1  if 1: append 1 to the partial copy of <j>
 
 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
 x4 1
 
 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> 
 y3 1 1 L y3 
 
 z1 0 1 L z1
 z1 1 1 R z2
 z2 0 
 z2 1 0 R f1  @(1) in <j> (done with copy<j>); go home, continue the multicopying loop  
 
 END COPY<j> SUBLOOP
 
 END GTM77 
 
Reclaiming unused "half-states"

In the machine GTM77, each of the five states (e6, q7, u2, v7, z2) is only "half used", and they can be eliminated by relabelling them as the complementary "unused halves" of the five states (e4, q4, s4, v4 , x4):
 e6 0 0 L h1  →  e4 0 0 L h1
 q7 1 0 R q8  →  q4 1 0 R q8
 u2 1 0 R v1  →  s4 1 0 R v1
 v7 1 0 R v8  →  v4 1 0 R v8
 z2 1 0 R f1  →  x4 1 0 R f1
yielding the following 72-state machine:
BEGIN GTM72
 
alphanumeric        numerical
state-labels        state-labels
------------        ------------
a1 0 1 L a2         01 0 1 L 02
a1 1 0 L a4         01 1 0 L 04
a2 0 0 L a3         02 0 0 L 03
a2 1 1 L a2         02 1 1 L 02
a3 0 1 R a3         03 0 1 R 03
a3 1 1 R a1         03 1 1 R 01
a4 0 0 L a5         04 0 0 L 05
a4 1 1 L a4         04 1 1 L 04
a5 0 1 L b1         05 0 1 L 06
a5 1                05 1   
b1 0 1 R b2         06 0 1 R 07
b1 1                06 1   
b2 0 0 R c1         07 0 0 R 08
b2 1 1 R b2         07 1 1 R 07
c1 0 0 L *          08 0 0 L 00
c1 1 1 L c2         08 1 1 L 09
c2 0 0 L c2         09 0 0 L 09
c2 1 1 L d1         09 1 1 L 10
d1 0 0 R d2         10 0 0 R 11
d1 1 1 R d1         10 1 1 R 10
d2 0 0 L e1         11 0 0 L 12
d2 1 1 R d1         11 1 1 R 10
e1 0 0 L e1         12 0 0 L 12
e1 1 0 L e2         12 1 0 L 13
e2 0 0 L e4         13 0 0 L 14
e2 1 1 L f1         13 1 1 L 16
e4 0 0 L h1         14 0 0 L 20
e4 1 0 L e5         14 1 0 L 15
e5 0 0 L g1         15 0 0 L 18
e5 1 1 R e4         15 1 1 R 14
f1 0 0 L f2         16 0 0 L 17
f1 1 1 L f1         16 1 1 L 16
f2 0 0 R p1         17 0 0 R 40
f2 1 1 L f1         17 1 1 L 16
g1 0 0 L g2         18 0 0 L 19
g1 1 1 L g1         18 1 1 L 18
g2 0 0 R b1         19 0 0 R 06
g2 1 1 L g1         19 1 1 L 18
h1 0 0 L h2         20 0 0 L 21
h1 1 1 L h1         20 1 1 L 20
h2 0 0 R i1         21 0 0 R 22
h2 1 1 L h1         21 1 1 L 20
i1 0 0 L i2         22 0 0 L 23
i1 1                22 1   
i2 0 1 R i3         23 0 1 R 24
i2 1                23 1   
i3 0 0 R i3         24 0 0 R 24
i3 1 0 R j1         24 1 0 R 25
j1 0 0 R j2         25 0 0 R 26
j1 1 1 R j1         25 1 1 R 25
j2 0 1 R j4         26 0 1 R 27
j2 1 1 R j1         26 1 1 R 25
j4 0 1 L k1         27 0 1 L 28
j4 1                27 1   
k1 0 0 L k2         28 0 0 L 29
k1 1 1 L k1         28 1 1 L 28
k2 0 0 R l1         29 0 0 R 30
k2 1 1 L k1         29 1 1 L 28
l1 0 0 L l2         30 0 0 L 31
l1 1                30 1   
l2 0 1 R l3         31 0 1 R 32
l2 1                31 1   
l3 0 0 R l3         32 0 0 R 32
l3 1 0 R l4         32 1 0 R 33
l4 0 0 L l6         33 0 0 L 35
l4 1 1 L l5         33 1 1 L 34
l5 0 0 R m1         34 0 0 R 37
l5 1                34 1   
l6 0 1 L l6         35 0 1 L 35
l6 1 1 L l7         35 1 1 L 36
l7 0 1 L p1         36 0 1 L 40
l7 1 1 L l7         36 1 1 L 36
m1 0 0 R m2         37 0 0 R 38
m1 1 1 R m1         37 1 1 R 37
m2 0 0 L m4         38 0 0 L 39
m2 1 1 R m1         38 1 1 R 37
m4 0 1 L k1         39 0 1 L 28
m4 1                39 1   
p1 0 0 L p2         40 0 0 L 41
p1 1                40 1   
p2 0 1 R p3         41 0 1 R 42
p2 1                41 1   
p3 0 0 R p3         42 0 0 R 42
p3 1 0 R p4         42 1 0 R 43
p4 0 0 L p6         43 0 0 L 45
p4 1 1 L p5         43 1 1 L 44
p5 0 0 R q1         44 0 0 R 47
p5 1                44 1   
p6 0 1 L p6         45 0 1 L 45
p6 1 1 L p7         45 1 1 L 46
p7 0 1 L b1         46 0 1 L 06
p7 1 1 L p7         46 1 1 L 46
q1 0 0 R q2         47 0 0 R 48
q1 1 1 R q1         47 1 1 R 47
q2 0 1 L q4         48 0 1 L 49
q2 1 1 R q1         48 1 1 R 47
q4 0 0 L q5         49 0 0 L 50
q4 1 0 R q8         49 1 0 R 52
q5 0 0 L q6         50 0 0 L 51
q5 1 1 L q5         50 1 1 L 50
q6 0 0 R q4         51 0 0 R 49
q6 1 1 L q6         51 1 1 L 51
q8 0 0 L u1         52 0 0 L 59
q8 1 1 R s1         52 1 1 R 53
s1 0 0 R s2         53 0 0 R 54
s1 1 1 R s1         53 1 1 R 53
s2 0 0 L s4         54 0 0 L 55
s2 1 1 R s1         54 1 1 R 53
s4 0 1 L t1         55 0 1 L 56
s4 1 0 R v1         55 1 0 R 60
t1 0 0 L t2         56 0 0 L 57
t1 1 1 L t1         56 1 1 L 56
t2 0 0 L t3         57 0 0 L 58
t2 1 1 L t2         57 1 1 L 57
t3 0 0 R q4         58 0 0 R 49
t3 1 1 L t3         58 1 1 L 58
u1 0 1 L u1         59 0 1 L 59
u1 1 1 R s4         59 1 1 R 55
v1 0 0 R v2         60 0 0 R 61
v1 1 1 R v1         60 1 1 R 60
v2 0 1 L v4         61 0 1 L 62
v2 1 1 R v1         61 1 1 R 60
v4 0 0 L v5         62 0 0 L 63
v4 1 0 R v8         62 1 0 R 65
v5 0 0 L v6         63 0 0 L 64
v5 1 1 L v5         63 1 1 L 63
v6 0 0 R v4         64 0 0 R 62
v6 1 1 L v6         64 1 1 L 64
v8 0 0 L z1         65 0 0 L 72
v8 1 1 R x1         65 1 1 R 66
x1 0 0 R x2         66 0 0 R 67
x1 1 1 R x1         66 1 1 R 66
x2 0 0 L x4         67 0 0 L 68
x2 1 1 R x1         67 1 1 R 66
x4 0 1 L y1         68 0 1 L 69
x4 1 0 R f1         68 1 0 R 16
y1 0 0 L y2         69 0 0 L 70
y1 1 1 L y1         69 1 1 L 69
y2 0 0 L y3         70 0 0 L 71
y2 1 1 L y2         70 1 1 L 70
y3 0 0 R v4         71 0 0 R 62
y3 1 1 L y3         71 1 1 L 71
z1 0 1 L z1         72 0 1 L 72
z1 1 1 R x4         72 1 1 R 68

END GTM72