## FANDOM

10,828 Pages

This blog post is about Turing Machines and bounds for $$\Sigma(n,m)$$

## Bounds

### Class 1 machines

The class 1 machines can be seen here

3 4 5
4 $$2^{\Sigma(2,5)}$$
5 $$2\uparrow^2\Sigma(2,5)$$
6 $$2^{\Sigma(3,3)}$$ $$2\uparrow^2\Sigma(2,4)$$
7 $$2\uparrow^3\Sigma(2,5)$$
8

### Class 2 machines

The class 2 machines are the machines in this blog post.

2 3 4 5
12 $$f_{\omega}(\Sigma(2,4))$$ $$f_{\omega}(\Sigma(2,5))$$
13 $$f_{\omega}(8)$$ $$f_{\omega}(\Sigma(3,4))$$ $$f_{\omega+1}(\Sigma(2,5))$$
14 $$f_{\omega}(\Sigma(3,3))$$
15 $$f_{\omega+1}(\Sigma(2,4))$$ $$f_{\omega+2}(\Sigma(2,5))$$
16 $$f_{\omega+1}(8)$$
17 $$f_{\omega+1}(\Sigma(3,3))$$ $$f_{\omega+2}(\Sigma(2,4))$$
18 $$f_{\omega}(\Sigma(5,2))$$ $$f_{\omega+2}(8)$$
19 $$f_{\omega}(\Sigma(6,2))$$ $$f_{\omega+2}(\Sigma(3,3))$$
21 $$f_{\omega+1}(8)$$
23 $$f_{\omega+1}^2(9)$$
24 $$f_{\omega+1}^3(32)$$
25 $$f_{\omega+1}^{12}(9)$$

### Class 3 machines

$$\Sigma(42,2) > f_{\omega2}(167)$$

$$\Sigma(26,3) > f_{\omega2}(\Sigma(3,3))$$

## Class 2 machines

### Ackermannian growth machines

11 state 3 color version:

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

10 state 4 color version:

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

This works for the following bounds:

$$\Sigma(13,3) > f_{\omega}(8)$$

$$\Sigma(14,3) > f_{\omega}(\Sigma(3,3))$$

$$\Sigma(12,4) > f_{\omega}(\Sigma(2,4))$$

### Extended version

We can extend it using 2 states: one to change row of 1s to 2s and a state to decrease group. Unfortunately, we need an additional color or an additional state beacause of technical reasons.  For a second extension we won't need the additional state. In 5-color version we can make the first extension with just 1 state because of state recycling.

This gives the following bounds:

$$\Sigma(16,3) > f_{\omega+1}(8)$$

$$\Sigma(17,3) > f_{\omega+1}(\Sigma(3,3))$$

$$\Sigma(18,3) > f_{\omega+2}(8)$$

$$\Sigma(19,3) > f_{\omega+2}(\Sigma(3,3))$$

$$\Sigma(15,4) > f_{\omega+1}(\Sigma(2,4))$$

$$\Sigma(17,4) > f_{\omega+2}(\Sigma(2,4))$$

$$\Sigma(13,5) > f_{\omega+1}(\Sigma(2,5))$$

$$\Sigma(15,5) > f_{\omega+2}(\Sigma(2,5))$$

## Class 3 machines

### $$\Sigma(42,2)$$

This machine outputs more than $$f_{\omega2}(n)$$ 1's if $$1\_\_(1\_)^n11$$ is entered

0 _ 1 l bb1
0 1 _ r bb2
bb1 _ 1 l bb2
bb1 1 1 l bb3
bb2 _ 1 r 0
bb2 1 _ l bb1
bb3 _ _ l bb4
bb3 1 _ l 18
bb4 _ 1 r bb2
bb4 1 1 l 0
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 _ 1 l 17
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 _ _ r halt
14 1 1 r 15
15 _ _ r 20
15 1 1 l 16
16 1 _ l 16
16 _ _ l 8
17 1 1 l 18
17 _ 1 l 1
18 _ _ l 19
18 1 _ l 19
19 1 1 l 18
19 _ 1 l 1
20 _ _ r halt
20 1 1 r 21
21 _ _ r 20
21 1 1 l 22
22 1 _ l 22
22 _ 1 l 23
23 1 1 l 35
23 _ 1 r 24
24 _ 1 l 25
24 1 1 r 31
25 1 1 l 25
25 _ 1 l 26
26 1 1 l 25
26 _ _ l 27
27 _ _ l 28
27 1 _ r 30
28 _ 1 r 29
28 1 1 r 27
29 _ _ r 29
29 1 1 r 30
30 1 1 r 30
30 _ 1 r 24
31 _ _ l 32
31 1 1 l 33
32 1 1 l 32
32 _ _ r 28
33 1 1 l 34
34 1 1 l 34
34 _ _ r 35
35 1 1 r 36
35 _ _ l 23
36 1 _ l 37
36 _ _ l 37
37 1 1 l 36
37 _ _ l 1

This proves $$\Sigma(42) > f_{\omega2}(167)$$

### $$\Sigma(26,3)$$

Previous machine with 3 colors.

0 _ 1 l bb1
0 1 2 r 0
0 2 1 r bb2
bb1 _ _ r 0
bb1 1 2 l bb1
bb1 2 1 r bb1
bb2 _ 1 l 22
bb2 1 1 l 0
bb2 2 1 l bb2
22 1 2 l 22
22 2 2 l 22
22 _ _ l 15
0a _ 1 r 0a
0a 1 _ l 0a
0a 2 1 r 1
1 1 2 l 3
1 2 2 r 2
1 _ _ r 12
2 _ _ r 12
2 2 2 r 2
2 1 2 l 8
3 2 1 l 3
3 1 1 l 3
3 _ 1 l 0a
4 2 1 r 5
4 1 1 l 4
4 _ 2 r 6
5 2 2 l 9
5 1 2 l 7
5 _ _ l 7
6 1 1 r 6
6 2 2 * 4
6 _ 2 r 8
7 1 1 l 7
7 2 2 l 7
7 _ 1 l 0a
8 2 2 l 8
8 1 1 r 4
8 _ _ r 18
9 1 1 l 9
9 2 2 l 9
9 _ 2 r 10
10 2 2 r 10
10 1 1 r 11
10 _ 1 l 0a
11 1 1 r 11
11 2 2 * 4
11 _ 1 l 13
12 _ 1 r halt
12 1 _ l 11
12 2 2 r 14
13 1 2 l 13
13 2 2 l 13
13 _ 1 l 0a
14 2 2 r 14
14 1 2 l 15
14 _ 1 r halt
15 2 _ l 16
15 _ 2 l 10
16 2 2 l 16
16 _ 1 l 17
17 2 1 l 17
17 1 1 l 17
17 _ _ l 6
18 _ 1 l 21
18 1 1 r 18
18 2 1 l 19
19 2 2 r 20
19 1 1 l 19
19 _ _ r 20
20 1 2 r 18
20 2 2 l 20
20 _ 1 l 0a
21 1 1 l 21
21 2 2 l 21
21 _ _ l 20

This proves $$\Sigma(26,3) > f_{\omega2}(\Sigma(3,3))$$