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
 

3 comments:

  1. Hi r.e.s., I'm excitedly analyzing your machine. I like it. You've taken a different approach than I was planning and I think it's been very successful!

    I have been simulating out using your GTM91 to try to get my head around it and your letterings of the states have been very helpful in breaking up the simulation into chunks.

    I've only gone over a bit over half of the machine, but I believe that you can cut at least 7 states (maybe 12 states).

    Consider:
    d1 0 0 R d2
    d1 1 1 R d1
    d2 0 0 L e1
    d2 1 1 R d3
    d3 0 0 L d1
    d3 1 1 L d1

    as far as I can tell, d3 only appears in these last three lines and thus you can actually cut out d3 and change the ref d3 -> d1. Why? Because, the only way you can end up in d3 is from (d2 1 1 R d3) which means you're in this configuration:
    d3 ?? 1 (?) ?? which (no matter what ? is) goes to:
    d1 ?? (1) ??? which goes to:
    d1 ?? 1 (?) ??

    So, you could have just gone (d2 1 1 R d1) in the first place.

    This looks like it will also work for f3, q3, h3, j3, k3, m3 (and glancing back at the transition table: maybe x3, v3, s3, g3 and even e3->f1)

    ReplyDelete
  2. Excellent catch! In addition to the 12 states you mentioned, it also allows removal of states r and w -- an overall reduction of 14 states. The revised machine, including the final 5-state reduction by reclaiming unused "half-states", has 72 states and reproduces the results of all the previous test cases (with about a 40% reduction in execution time).

    If you don't mind, I'll simply edit these changes into the above posting and call the revised machine GTM72.

    Another major reduction seems likely by eliminating the virtual duplication (in blocks v-z) of the (now) 15 states in blocks q-u.

    ReplyDelete
  3. I've eliminated another 8 states -- bringing the total now to 64 states -- and added a new posting that describes the resulting machine (GTM64).

    Four states are eliminated by restricting the rewriting algorithm to ordinals less than ω2 (instead of ω^2), and correspondingly changing the initialisation stage (still with 5 states) to write <0><1><2> onto the all-0 tape. The number computed is now h_(ω+2)(0) + 1 >> G, instead of the unnecessarily-large h_(ω2+1)(0) + 1. This allows blocks q-u to be replaced by simpler code not involving a loop.

    Four additional states eliminated are c2, e6, l5, and p5, which were superfluous. (The half-state e6 0 had been relabelled as the until-then-unused half-state e4 0, so eliminating e6 frees up the half-state e4 1 to be relabelled as some other unused "half-state", e.g. b1 1.)

    PS:
    A notable aspect of this "half-state relabelling" business is that a half-state to be eliminated can be relabelled as any unused half-state that matches it -- anywhere in a TM "program" -- even when there is no "logical connection" between the two half-states being merged into one state; e.g., merging e4 (about pair-reduction) into b1 (about incrementing n). This seriously obfuscates a program merely for the sake of making it smaller. (This reminds me a lot of the goto-laden "spaghetti code" that was more common before the era of "structured programming".) This may help to see why the "logic" of a smallest-program-accomplishing-so-and-so may be virtually impenetrable by human understanding.

    ReplyDelete