FANDOM


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))\)

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.