# Okay, more Turing machines

Thought I would join in the fun.

### Doubling a string of ones

A 3-state, 2-color machine that doubles the length of the input string:

0 1 _ l 1
0 _ _ l halt
1 1 1 l 1
1 _ 1 r 2
2 1 1 r 2
2 _ 1 r 0


### Implementing 2^m

Given a string of m ones, outputs a string of 2^m ones:

0 1 _ l 5
0 _ 1 r halt
5 1 1 l 5
5 _ _ r 3
3 1 _ l 1
3 _ 1 r 4
1 1 1 l 1
1 _ 1 r 2
2 1 1 r 2
2 _ 1 r 3
4 1 _ l 5
4 _ 1 r halt


### Implementing 2^^m

After some trial and error, this program takes m to 2^^m:

0 _ _ l 6
0 1 1 l 10
1 1 1 l 1
1 _ 1 r 2
2 1 1 r 2
2 _ 1 r 3
3 1 _ l 1
3 _ 1 r 4
4 1 _ l 5
4 _ 1 r 7
5 1 1 l 5
5 _ _ r 3
6 1 1 l 6
6 _ _ r 9
7 _ _ r 8
8 1 _ l 0
8 _ _ l halt
9 1 _ l 5
9 _ 1 r 7
10 _ _ l 9


### Implementing $$2 \uparrow^k m$$

Okay, I've finally figured out a general rule for $$2 \uparrow^k m$$. We start with a more systematic TM for $$m \mapsto 2^m$$:

0 1 1 r 0
0 _ _ l 7
1 1 _ r 2
1 _ 1 l 6
2 1 1 r 2
2 _ 1 l 3
3 1 1 l 3
3 _ 1 l 1
4 1 1 r 4
4 _ _ l 1
5 1 _ r 4
5 _ 1 l 6
6 _ 1 l 7
6 1 1 l 7
7 1 _ r 5
7 _ _ r halt


Starting from a TM with 6k + 2 states for $$2 \uparrow^k m$$, we can generate a TM with 6k + 8 states for $$2 \uparrow^{k+1} m$$ as follows:

0 1 1 r 0
0 _ _ l 1
1 1 _ r 1
1 _ 1 l 6k+6

;TM for $$2 \uparrow^k m$$ goes here incremented by 2 steps

6k+4 1 1 r 6k+4
6k+4 _ _ l 6k+5
6k+5 1 _ l 6k+6
6k+6 1 1 l 6k+6
6k+6 _ 1 l 6k+7
6k+7 1 _ r 2
6k+7 _ _ r halt


So we have $$2 \uparrow^k m$$ implementable with 6k + 2 states.

## Restricted Knuth Notation with 3 symbols

LittlePeng9 implemented "Restricted Knuth Notation" with 17 states and 4 symbols, and also 37 states and 2 symbols. Here is an implementation with 18 states and 3 symbols.

0 x x r 0
0 ^ ^ r 0
0 _ _ l 1
1 x x l 1
1 _ _ r halt
1 ^ x l 2
2 x x l 1
2 ^ ^ r 3
3 x x r 4
4 x x r 5
5 _ _ l 6
5 x x l 10
6 x _ l 6
6 ^ _ l 7
7 ^ _ l 7
7 x x r 8
8 _ x r 9
9 _ x l 1
10 x ^ l 11
11 x x l 15
12 ^ ^ r 12
12 x ^ r 13
13 x x r 13
13 _ x l 14
14 x x l 14
14 ^ ^ l 14
14 _ _ l 15
15 _ _ l 15
15 ^ _ r 16
15 x x r 17
16 _ _ r 16
16 x x r 12
17 _ ^ r 17
17 x x  r 0


## Expandal Arrays with 3 symbols

By adding just 4 states, we can make the previous Turing machine into a function that iterates the Hyper function m times!

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


The function satisfies the following:

f(1) = 3
f(n + 1) = Hyper (2, 3, f(n)) - 1


We have f(67) > Graham's number, so if we can start the function with 67 non-blank symbols, we can beat Graham's number. Unfortunately, I'm having a really hard time getting just 67 symbols, the best I can do is 9 states, which is just terrible. Milton Green was able to do better with 7 states and 2 symbols somehow!

0 _ x r 8
8 _ x r 7
7 x x r 7
7 _ _ r 5
5 x x r 5
5 _ _ r 1
1 x ^ r 1
1 _ x l 2
2 ^ x r 3
2 x x l 2
2 _ x l 4
3 x x r 3
3 _ x l 2
4 _ x l 6
4 x _ r 1
6 _ x l halt
6 x _ r 5


This proves that BB(31, 3) > Graham's number. But I'm not really satisfied, since I'm sure we can do much better than 9 states to get 67 symbols.

Update: I've found the answer, by looking at the Busy Beaver candidates. It turns out the best Busy Beaver candidate for 3-state, 3-symbol Turing machines produces a contiguous string of 374,676,383 non-blank symbols. So running the Busy Beaver candidate, and then applying our function, yields more than $$f_{\omega+1}(374,676,380)$$ non-blank symbols, which of course exceeds Graham's number. So we have proven that $$\Sigma(25,3)$$ > Graham's number.

## A New Record! Beating Graham's number with a 2-symbol TM

Here we define a 25-state, 2-symbol TM that outputs more than Graham's number of ones. This reduces the record for beating Graham's number from 64 states down to 25 states.

### Ackermannian growth with 13 states

First, we define a 13-state TM that generates Ackermannian numbers:

0 1 1 l 0
0 _ 1 r 2    ;add one to leftmost group, then move right
2 1 1 r 2
2 _ _ r 3
3 _ _ l halt ;if no more groups, halt
3 1 1 r 4    ;search for leftmost group after first group with more than one 1 - call it group n
4 1 1 l 5
4 _ _ r 6
5 1 _ l 5
5 _ 1 l 0
6 _ _ l halt ;if no such group, halt
6 1 1 r 7
7 _ _ r 6
7 1 1 l 8
8 1 _ l 9    ;decrement group n
9 _ _ l 10   ;move 1's from group 1 to group n-1
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


Basically, this TM takes as input a sequence of strings of 1's. It adds one 1 to the first string, then repeatedly performs the following operation:

1. If string 2 has more than one 1, decrease it by one and increase string 1 by 2. 2. If string 2 has just one 1, let string n be the first string after string 1 with more than one 1. Decrease string n by 1, increase string n-1 to the length of string 1 plus 1, and decrease string 1 to 3.

In other words, if we represent the strings as $$(a_1, a_2, \ldots, a_m$$, then we use the following rules:

$$(a_1, a_2 + 1, \ldots, a_m) \mapsto (a_1 + 2, a_2, \ldots, a_m)$$

$$(a_1, 1, \ldots, 1, a_n + 1, \ldots, a_m) \mapsto (3, 1, \ldots, a_1 + 1, a_n, \ldots, a_m)$$

We have the following outputs for some specified inputs:

$$(n) \mapsto (n+1)$$

$$(1, n) \mapsto (2n, 1)$$

$$(1, 1, n) \mapsto (5*2^n - 3, 1, 1)$$

$$(1, 1, 1, n) \mapsto (m, 1, 1, 1)$$ where $$m > 2 \uparrow\uparrow (n+1)$$

$$(1, 1, 1, 1, n) \mapsto (m, 1, 1, 1, 1)$$ where $$m > 2 \uparrow\uparrow\uparrow (n+1)$$

and in general, $$(1\_)^{m+1} 1^n \mapsto k (\_1)^{m+1}$$, where $$k > 2 \uparrow^m (n+1)$$. So we are able to exhibit Ackermannian growth with just 13 states and 2 symbols.

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.

Similarly, we can use the 6-state Busy Beaver candidate by Kropitz which outputs $$(11\_)^K 111$$ where $$K > 1.75 * 10^{18267}$$. This leads to $$\Sigma(19) > 2 \uparrow^{1.75 * 10^{18267}} 4$$.

### Expandal growth rate with 17 states

By adding just four states, we increase the growth rate to $$f_{\omega+1}(n)$$.

0 1 1 l 0
0 _ 1 r 2    ;add one to leftmost group, then move right
2 1 1 r 2
2 _ _ r 3
3 _ _ r 14   ;if no more groups, halt
3 1 1 r 4    ;search for leftmost group after first group with more than one 1 - call it group n
4 1 1 l 5
4 _ _ r 6
5 1 _ l 5
5 _ 1 l 0
6 _ _ r 14   ;if no such group, halt
6 1 1 r 7
7 _ _ r 6
7 1 1 l 8
8 1 _ l 9    ;decrement group n
8 _ _ l 15
9 _ _ l 10   ;move 1's from group 1 to group n-1
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 ;if rightmost string is empty, halt
14 1 _ l 8    ;decrement rightmost string
15 _ 1 l 16   ;change sequence of strings to alternating _'s and 1's
16 1 1 l 17
16 _ 1 l 0
17 _ _ l 16
17 1 _ l 16


For the input, in addition to the sequence of strings of 1's separated by a blank, there is an extra string on the right separated from the rest of the strings by two blanks. The TM evaulates the leftmost sequence of strings according to the last TM, until it reaches a halting situation; in that case it decrements the extra string by one, and replaces the initial sequence of strings with (2, 1, ..., 1, 2), where the new sequence is about as long as the old sequence (it's two or three characters longer, not that that matters much.). If the old sequence had length $$m$$, the new sequence will evaluate to a sequence of length about $$f_{\omega}(m/2)$$. So if the extra string has length $$n$$, we will generate a sequence of length about $$f_{\omega+1}(n)$$. (The division by 2 doesn't really matter except at the beginning).

For some specific inputs:

1 leads to 11. 1__1 leads to 1111_1. 1__11 leads to $$1^{21} \_ 1 \_ 1 \_ 1 \_ 1$$. 1__111 leads to more than $$2 \uparrow^{13} 3$$ 1's.

As 1__13 leads to more than $$G_1$$ 1's, we simply need the extra string to be of length at least 66. That is, we want an input of $$1 \_ \_ 1^n$$ where $$n \ge 66$$.

### The record TM

I was able to generate a satisfactory input string using 8 states.

0 _ 1 r b
0 1 _ l d
b _ 1 l c
b 1 1 r d
c _ 1 l 0
c 1 1 l c
d _ 1 r 18
d 1 1 r e
e _ 1 r 0
e 1 _ r b
18 1 1 l 18
18 _ 1 l 19
19 1 1 l 18
19 _ _ l 20
20 _ _ l 1
1 1 1 l 1
1 _ 1 r 2
2 1 1 r 2
2 _ _ r 3
3 _ _ r 14
3 1 1 r 4
4 1 1 l 5
4 _ _ r 6
5 1 _ l 5
5 _ 1 l 1
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


This TM starts with the same 5-state Busy Beaver candidate as before, generating $$111(\_11)^{2047}$$. The states 18, 19, and 20 moves left and replaces $$111(\_11)^{2047}$$ with $$1 \_ \_ (1)^{6146}$$, and then evaluates the previous TM. This leads to a sequence of greater than $$f_{\omega+1} (6143)$$ 1's, which indeed exceeds Graham's number. So $$\Sigma(25) >$$ Graham's number.

With 26 states, we can use the 6-state Busy Beaver candidate by Kropitz, which will generate more than $$f_{\omega+1} (5.25 * 10^{18267})$$ 1's.

Possible improvement: can we generate $$1 \_ \_ 1^n$$ where $$n \ge 66$$ with fewer than 8 states? Or can we improve the basic algorithm? Any help would be greatly appreciated. But anyway, I'm pretty satisfied with cutting the number from 64 to 25.