Googology Wiki
Register
Advertisement
Googology Wiki

I found some improvements to Deedlit's original Ackermannian growth and expandal Turing Machines.

Using this, I can prove that \(\Sigma(19) > f_{\omega+1}(163) > G\).

Note: I found a machine that proves \[\Sigma(18) > f_{\omega+1}(7\cdot10^{57}) > G.\]

Machines that need input[]

10 state, 2 color machine with Ackermannian growth[]

Somehow states 3, 4 and 5 are completely obsolete in the original machine.

In fact, removing them even increases the first string by three ones instead of two.

0 1 1 l 0
0 _ 1 r 2
2 1 1 r 2
2 _ _ r 6
6 _ _ l halt
6 1 1 r 7
7 _ _ r 6
7 1 1 l 8
8 1 _ l 9
9 _ _ l 10
9 1 1 r 11
10 1 1 l 9
10 _ 1 r 0
11 1 _ r 12
11 _ _ l 13
12 _ 1 r 11
12 1 1 l 13
13 1 1 l 13
13 _ 1 l 10

You can simulate the machine on Anthony Morphett's site.

14 state, 2 color machine with expandal growth[]

This also works in the expandal growth machine, as that is just an extension of the Ackermannian machine.

0 1 1 l 0
0 _ 1 r 2  
2 1 1 r 2
2 _ _ r 6
6 _ _ r 14  
6 1 1 r 7
7 _ _ r 6
7 1 1 l 8
8 1 _ l 9  
8 _ _ l 15
9 _ _ l 10   
9 1 1 r 11
10 1 1 l 9
10 _ 1 r 0
11 1 _ r 12
11 _ _ l 13
12 _ 1 r 11
12 1 1 l 13
13 1 1 l 13
13 _ 1 l 10
14 _ _ l halt 
14 1 _ l 8   
15 _ 1 l 16   
16 1 1 l 17
16 _ 1 l 0
17 _ _ l 16
17 1 _ l 16

14 state, 2 color machine with expandal growth, variant[]

0 1 1 l 0
0 _ 1 r 2  
2 1 1 r 2
2 _ _ r 6
6 _ _ r 14  
6 1 1 r 7
7 _ _ r 6
7 1 1 l 8
8 1 _ l 9  
8 _ 1 l 16  
9 _ _ l 10   
9 1 1 r 11
10 1 1 l 9
10 _ 1 r 0
11 1 _ r 12
11 _ _ l 13
12 _ 1 r 11
12 1 1 l 13
13 1 1 l 13
13 _ 1 l 10
14 _ _ l halt 
14 1 _ l 15   
15 _ _ l 8
16 1 1 l 17
16 _ 1 l 0
17 _ _ l 16
17 1 _ l 16

I switched state 15 and a part of state 8. Both of these parts are added in the expandal machine and are only accessed using state 14. They can therefore be switched.

This machine can also be simulated on Anthony Morphett's site.

14 state, 2 color machine with expandal growth, second variant[]

0 1 1 l 0
0 _ 1 r 2
2 1 1 r 2
2 _ _ r 6
6 _ 1 r 14 
6 1 1 r 7
7 _ _ r 6
7 1 1 l 8
8 1 _ l 9 
8 _ 1 l 16 
9 _ _ l 10  
9 1 1 r 11
10 1 1 l 9
10 _ 1 r 0
11 1 _ r 12
11 _ _ l 13
12 _ 1 r 11
12 1 1 l 13
13 1 1 l 13
13 _ 1 l 10
14 _ _ r halt
14 1 _ l 15
15 1 _ l 8
16 1 1 l 17
16 _ 1 l 0
17 _ _ l 16
17 1 _ l 16

In state 6, we now write a one instead of a zero. This is changed back in state 15.

This machine can also be simulated on Anthony Morphett's site.

17 state, 2 color machine with multiexpandal (\(f_{\omega+2}(n)\)) growth[]

0 1 1 l 0
0 _ 1 r 2
2 1 1 r 2
2 _ _ r 6
6 _ 1 r 14 
6 1 1 r 7
7 _ _ r 6
7 1 1 l 8
8 1 _ l 9 
8 _ 1 l 16 
9 _ _ l 10  
9 1 1 r 11
10 1 1 l 9
10 _ 1 r 0
11 1 _ r 12
11 _ _ l 13
12 _ 1 r 11
12 1 1 l 13
13 1 1 l 13
13 _ 1 l 10
14 _ _ r 18
14 1 _ l 15
15 1 _ l 8
16 1 1 l 17
16 _ 1 l 0
17 _ _ l 16
17 1 _ l 16
18 _ _ r halt
18 1 _ l 19
19 _ 1 l 20
19 1 1 l 19
20 _ _ l 17
20 1 1 l 19

This machine can also be simulated on Anthony Morphett's site.

Explanation: When given input \(1\_\_\_1^n\), it returns approximately \(f_{\omega+2}(n)\) ones.

When the one after three spaces is reached, we are in state 18. This changes this one to a space, then changes the current tape into a string of ones and writes two spaces and an one in front of it. So the whole string of ones is now in the expandal group. So every one has the effect of taking \(m\) ones in the first group to more than \(m\) ones in the expandal group. This hence iterates expandal growth and reaches hence multiexpandal (\(f_{\omega+2}(n)\)) growth.

20 state, 2 color machine with powerexpandal (\(f_{\omega+3}(n)\)) growth[]

0 1 1 l 0
0 _ 1 r 2
2 1 1 r 2
2 _ _ r 6
6 _ 1 r 14 
6 1 1 r 7
7 _ _ r 6
7 1 1 l 8
8 1 _ l 9 
8 _ 1 l 16 
9 _ _ l 10  
9 1 1 r 11
10 1 1 l 9
10 _ 1 r 0
11 1 _ r 12
11 _ _ l 13
12 _ 1 r 11
12 1 1 l 13
13 1 1 l 13
13 _ 1 l 10
14 _ _ r 18
14 1 _ l 15
15 1 _ l 8
16 1 1 l 17
16 _ 1 l 0
17 _ _ l 16
17 1 _ l 16
18 _ 1 r 21
18 1 _ l 19
19 _ 1 l 20
19 1 1 l 19
20 _ _ l 17
20 1 1 l 19
21 _ _ r halt
21 1 _ l 22
22 _ 1 l 23
22 1 1 l 22
23 _ _ l 20
23 1 1 l 22

This machine can also be simulated on Anthony Morphett's site.

Explanation: When given input \(1\_\_\_\_1^n\), it returns approximately \(f_{\omega+3}(n)\) ones.

When the one after three spaces is reached, we are in state 21. This changes this one to a space, then changes the current tape into a string of ones and writes three spaces and an one in front of it. So the whole string of ones is now in the multiexpandal group. So every one has the effect of taking \(m\) ones in the first group to more than \(m\) ones in the multiexpandal group. This hence iterates multiexpandal growth and reaches hence powerexpandal (\(f_{\omega+3}(n)\)) growth.

Machines that don't need input[]

5 state, 2 color machine that outputs 165 consecutive ones[]

The following machine:

0 _ 1 l b
0 1 1 r 0
b _ 1 l c
b 1 1 r e
c _ 1 l d
c 1 1 l e
d _ _ r 0
d 1 1 l c
e 1 _ r b
e _ 1 l halt

halts in 15,589 steps, outputing the following tape:

_11111111...[150 ones omitted]...1111111
^

Source: Mathematica Journal 2009.

15 state, 2 color machine that outputs more than \(f_{\omega}(2046)\) non-zero symbols[]

Deedlit already notes in the original post that:

"Using a 5-state Busy Beaver candidate found by Marxen and Buntrock, we can output \((11\_)^{2047} 111\) using 5 states. So if we then run our TM, we will output a number \(> 2 \uparrow^{2046} 4\). So \(\Sigma(18) > 2 \uparrow^{2046} 4\). I believe this is stronger than any known bound."

This will also be subject to the three state reduction, so \(\Sigma(15) > 2 \uparrow^{2046} 4\).

Using FGH, we can write this as \(\Sigma(15) > f_{\omega}(2046)\).

16 state, 2 color machine that outputs more than \(f_{\omega}(f_{\omega}(5))\) non-zero symbols[]

As this is just a minor result, I won't go to deep into the details, unless requested in the comments.

See and simulate the machine on Anthony Morphett's site.

After over 18,000 steps, the tape looks like this:

111111111111_1_11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111_111111111_11_111_111_11_1__1

Every one in the third group triples the number of ones in the first. The fourth group corresponds therefore to repeatedly taking \(3^n\), the fifth to repeatedly taking \(3\uparrow\uparrow n > f_3(n)\), the sixth to repeatedly taking \(3\uparrow\uparrow\uparrow n > f_4(n)\) and the seventh to repeatedly taking \(3\uparrow\uparrow\uparrow\uparrow n > f_5(n)\).

Therefore, this will reduce to

111111...[l ones omitted]...11111__1

with \(l > f_5(f_4(f_4(f_3(f_3(3^{3^{120}}))))) > 2 \cdot f_5(5) = 2 \cdot f_{\omega}(5)\).

Therefore, this will finally reduce to more than \(f_{\omega}(f_{\omega}(5))\) non-zero symbols.

17 state, 2 color machine that outputs more than \(f_{\omega+1}(10)\) non-zero symbols[]

This one uses the first variant of the expandal machine.

State 15 and state 2' of the 4 state, 2 color Busy Beaver can be reduced into one state by making the halting rule of the 4 state, 2 color Busy Beaver work like state 15 in the variant of the expandal machine.

0 _ 1 r 1'
0 1 1 l 1'
1' _ 1 l 0
1' 1 _ l 2'
2' _ _ l 8
2' 1 1 l 3'
3' _ 1 r 3'
3' 1 _ r 0

1 1 1 l 1
1 _ 1 r 2 
2 1 1 r 2
2 _ _ r 6
6 _ _ r 14 
6 1 1 r 7
7 _ _ r 6
7 1 1 l 8
8 1 _ l 9 
8 _ 1 l 16 
9 _ _ l 10  
9 1 1 r 11
10 1 1 l 9
10 _ 1 r 1
11 1 _ r 12
11 _ _ l 13
12 _ 1 r 11
12 1 1 l 13
13 1 1 l 13
13 _ 1 l 10
14 _ _ l halt
14 1 _ l 2'
16 1 1 l 17
16 _ 1 l 1
17 _ _ l 16
17 1 _ l 16

Note: states 0 and 1', 2', 3'  are a variant of the 4 state, 2 color Busy Beaver.

The machine can be simulated online on Anthony Morphett's site.

After 110 steps, the tape looks like:

111__111111111111

There are 12 ones, therefore the machine outputs more than \(f_{\omega+1}(10)\) symbols.

Rest of the argument goes similiar to that in the 18 state version.

18 state, 2 color machine that outputs more than \(f_{\omega+1}(7 \cdot 10^{57})\) non-zero symbols[]

0 1 _ l 8
0 _ 1 l 18
0' 1 1 l 0'
0' _ 1 r 2
2 1 1 r 2
2 _ _ r 6
6 _ 1 r 14  
6 1 1 r 7
7 _ _ r 6
7 1 1 l 8
8 1 _ l 9  
8 _ 1 l 16  
9 _ _ l 10   
9 1 1 r 11
10 1 1 l 9
10 _ 1 r 0'
11 1 _ r 12
11 _ _ l 13
12 _ 1 r 11
12 1 1 l 13
13 1 1 l 13
13 _ 1 l 10
14 _ _ r 18
14 1 _ l 0
16 1 1 l 17
16 _ 1 l 0'
17 _ _ l 16
17 1 _ l 16
18 _ 1 r 21
18 1 _ l 19
19 _ 1 l 20
19 1 1 l 19
20 _ _ l 17
20 1 1 l 19
21 1 1 r 0
21 _ _ r halt

This machine can be simulated online on Anthony Morphett's site

Note: State 0 has been renamed to state 0' and state 15 has been renamed to state 0. State 21 has been added.

Sketch of the proof that this machine outputs more than \(f_{\omega+1}(7 \cdot 10^{57})\) ones[]

First, we have to prove that the multiexpandal machine indeed exhibits multiexpandal growth.

For this, we can prove by induction that the Ackermannian growth machine indeed has Ackermannian growth. Then, another induction shows that the expandal machine indeed exhibits expandal growth. The third induction should work to show that it gives multiexpandal growth. (Details might be added later, but it is a lot of writing. If anyone else wants to do this, please do so!).

Now a note on the moved halting state: this has only effect when there is another symbol after the last one in the multiexpandal group. This never occurs but in the beginning, where it saves a state in setting the input.

After 10 steps, the tape looks like:

1__11_1

When the 14 state machines (or the 17 state machine, for that matter) are given the input \(1\_\_11\), after approximately 35,000 steps, the following tape is created:

11111...[110 ones omitted]...11111_1_11111...[107 ones omitted]...11111_1_1

Every one in the third group more than triples the number of ones in the first group. So there are over \(120\cdot 3^{117} > 7 \cdot 10^{57}\) ones on the tape when this halts.

This means that the tape will look eventually like

11111...[k ones omitted]...11111_1_1_1_1___1

with \(k>7\cdot10^{57}\).

This will be transformed to

1__111111...[k ones omitted]...111111111111111

Note again that \(1\_\_11\) gives more than \(7\cdot10^{57}\) ones.

Then, for every extra one after the double space, the machine takes \(m\) ones to more than \(g(n)=f_{\omega}(\frac{m}{2})\) ones. Note that \(g^k(n+1)> f_{\omega}^k(\frac{n}{2})\). (This requires a proof. It would be easier to show that \(g^k(n) > f_{\omega}^{\frac{k}{2}}(\frac{n}{2})\), but it is weaker. It would still be enough to beat Graham's Number, though). 

This means that the total number of ones will be greater than \[f^{7 \cdot 10^{57}}_{\omega}(7 \cdot 10^{57}) = f_{\omega+1}(7 \cdot 10^{57})\]

This means that \(\Sigma(18) > f_{\omega+1}(7 \cdot 10^{57}) > G\).

19 state, 2 color machine that outputs more than \(f_{\omega+1}(163)\) non-zero symbols[]

0 _ 1 l 18
0 1 1 r 0
1 1 1 l 1
1 _ 1 r 2 
2 1 1 r 2
2 _ _ r 6
6 _ _ r 14 
6 1 1 r 7
7 _ _ r 6
7 1 1 l 8
8 1 _ l 9 
8 _ _ l 15
9 _ _ l 10  
9 1 1 r 11
10 1 1 l 9
10 _ 1 r 1
11 1 _ r 12
11 _ _ l 13
12 _ 1 r 11
12 1 1 l 13
13 1 1 l 13
13 _ 1 l 10
14 _ _ l halt
14 1 _ l 8  
15 _ 1 l 16  
16 1 1 l 17
16 _ 1 l 1
17 _ _ l 16
17 1 _ l 16
18 _ 1 l 19
18 1 1 r 21
19 _ 1 l 20
19 1 1 l 21
20 _ _ r 0
20 1 1 l 19
21 1 _ r 18
21 _ _ l 8

This machine can be simulated online on Anthony Morphett's site.

Note: states 0 and 18, 19, 20 and 21 form the machine from Mathematica Journal, mentioned in the first section.

This machine is kept for historical reasons only. This was the record holder for the lowest number of states to beat Graham's Number for a few hours.

19 state, 2 color machine that outputs more than \(f_{\omega+1}^3(9)\) non-zero symbols[]

See and simulate this machine on Anthony Morphett's site.

After 62 steps, the tape looks like:

1__11111111111_11

There are eleven ones, so the part up to the last space gives at least \(f_{\omega+1}(9)\) ones. Then the remaining ones each take \(f_{\omega+1}(n)\) of the number of ones, giving a total of more than \(f_{\omega+1}^3(9)\) non-zero symbols.

20 state, 2 color machine that outputs more than \(f_{\omega+1}^4(7\cdot10^{57})\) non-zero symbols[]

See and simulate this machine on Anthony Morphett's site

After 19 steps, the tape looks like:

1__11_1111

We know the first part returns over \(7\cdot10^{57}\) ones. Then the remaining ones after the third space each take \(f_{\omega+1}(n)\) of the number of ones, giving a total of more than \(f_{\omega+1}^4(7\cdot10^{57})\) non-zero symbols.

21 state, 2 color machine that outputs more than \(f_{\omega+2}(f_{\omega+1}^2(4))\) non-zero symbols[]

See and simulate this machine on Anthony Morphett's site

After 26 steps, the tape looks like:

1__111111_1_1

We know the first part returns over \(f_{\omega+1}(4)\) ones. The next-to last one takes \(f_{\omega+1}(n)\) of the number of ones, the last one takes \(f_{\omega+2}(n)\) of the number of ones, giving a total of \(f_{\omega+2}(f_{\omega+1}^2(4))\)

22 state, 2 color machine that outputs more than \(f_{\omega+2}^3(f_{\omega+1}(4))\) non-zero symbols[]

See and simulate this machine on Anthony Morphett's site


After 27 steps, the tape looks like:

1__111111__111

We know the first part returns over \(f_{\omega+1}(4)\) ones. Then the last three bring the total to more than \(f_{\omega+2}^3(f_{\omega+1}(4))\).

Table of bounds[]

Under construction, will be updated later.

\(n\) Lower bound for \(\Sigma(n)\) Notes
15 \(f_{\omega}(2046)\) Based on Marxen & Buntrock's \(\Sigma(5)\) runner-up and Deedlit's Ackermannian growth machine.
16 \(f_{\omega}^2(5)\) Based on Deedlit's expandal growth machine.
17 \(f_{\omega+1}(10)\) Based on Deedlit's expandal growth machine.
18 \(f_{\omega+1}(7\cdot10^{57})\)

Based on the multiexpandal growth machine, which is based on Deedlit's expandal growth machine.

Currently smallest known 2 color machine that beats Graham's number.

19 \(f_{\omega+1}^3(9)\) Based on the multiexpandal growth machine, which is based on Deedlit's expandal growth machine.
20 \(f_{\omega+1}^4(7\cdot10^{57})\) Based on the multiexpandal growth machine, which is based on Deedlit's expandal growth machine.
21 \(f_{\omega+2}(f_{\omega+1}^2(4))\) Based on the powerexpandal growth machine, which is based on Deedlit's expandal growth machine.
22 \(f_{\omega+2}^3(f_{\omega+1}(4))\) Based on the powerexpandal growth machine, which is based on Deedlit's expandal growth machine.


Here is a list of record holders:

  • September 9, 2010: r.e.s. proves that \(\Sigma(64) > G\).
  • April 8, 2013: Deedlit11 proves that \(\Sigma(25) > G\).
  • September 27, 2013: Wythagoras proves that \(\Sigma(24) > G\) using Deedlit11's results.
  • October 6, 2013: Wythagoras proves that \(\Sigma(23) > G\) using Deedlit11's results.
  • August 5, 2014: Wythagoras proves that \(\Sigma(22) > G\) using Deedlit11's results.
  • July 24, 2016: Wythagoras proves that \(\Sigma(19) > G\) using Deedlit11's results.
  • July 24, 2016: Wythagoras proves that \(\Sigma(18) > G\) using Deedlit11's results.


I think we finally exhausted improving Deedlit's result, but I have thought that three times now.


I wonder which of you [Deedlit11 or Wythagoras] will first prove BB(20)>G
  —LittlePeng9, October 7, 2013


I think that Sigma(17) > G will be proven in five years, but if n is the number of states to beat G, I think that even Sigma(n+2) > G won't be proven within 15 years.
  —Wythagoras, August 6, 2014
Advertisement