FANDOM


Below is the list of Turing machines programmed by me with their description. You can simulate all these program here.

Despite that these programs are written for the simulator above, you can also rewrite them for the simulator with "computing" ability (run program without showing steps), which is placed here.

Also I decided to write comments for each rule to make it clear for me and other people.

Concatenating two strings of ones

Enter two strings and TM concatenates it (separate it by only one space).

Code:

0 _ * l halt ; If no string remain to concatenate, then simply halt (brake).
0 1 _ r 1 ; Remove 1 to replace it further at the end of second string.
1 1 * r 1 ; We travel first string until we reach blank.
1 _ * r 2 ; When blank is reached, start the cycle for traveling second string.
2 1 * r 2 ; Traveling second string.
2 _ 1 l 3 ; When blank is reached, append 1 at the end.
3 1 * l 3 ; Traveling second string again, but to the left in this case.
3 _ * l 4 ; Prepare to travel first string.
4 1 * l 4 ; Traveling first string.
4 _ * r 0 ; Iterate the cycle.


Concatenating multiple strings of ones

Enter arbitrary number of strings and TM concatenates it (separate it by only one space).

Code:

0 _ * r 5 ; When two string being concatenated, we look whether any string remain or not.
0 1 _ r 1 ; Remove 1 to replace it further at the end of second string.
1 1 * r 1 ; We travel first string until we reach blank.
1 _ * r 2 ; When blank is reached, start the cycle for traveling second string.
2 1 * r 2 ; Traveling second string.
2 _ 1 l 3 ; When blank is reached, append 1 at the end.
3 1 * l 3 ; Traveling second string again, but to the left in this case.
3 _ * l 4 ; Prepare to travel first string.
4 1 * l 4 ; Traveling first string.
4 _ * r 0 ; Iterate the appending cycle.
5 _ * r 6 ; When blank is reached, we check whether any string remains.
5 1 * r 5 ; Traveling resulting string to check other strings for concatenating.
6 _ * r halt ; If no string remains, then halt.
6 1 * l 7 ; If any string remains, then we start to iterate the cycle.
7 _ * l 8 ; After applying previous rule, we necessarily stumble on blank.
8 1 * l 8 ; Traveling first string.
8 _ * r 0 ; Iterate the concatenating cycle.

Removing one string of ones from other

Enter two strings and TM remove the one string from other.

Code:

0 1 * r 0 ; Immediately travel to the second string for removing 1 from it.
0 _ * r 1 ; When blank is reached, go to the second string.
1 _ * l 2 ; After traveling second string, we go need to remove 1 at the end.
1 1 * r 1 ; Traveling second string.
2 _ * r halt ; If there is no ones in subtrahend, then halt.
2 1 _ l 3 ; Remove 1 at the end of the second string.
3 1 * l 3 ; Traveling second string to the left.
3 _ * l 4 ; When blank is reached, go to the first string for removing 1 from it.
4 1 * l 4 ; Traveling first string to the left.
4 _ * r 5 ; When blank is reached, go to the state 5 that remove 1 from the first string.
5 1 _ r 0 ; Iterate the one-to-one correspondence cycle.
5 _ * r halt ; If blank entered at the first in the input string, then just halt (illegal input).

Double string of ones in size

Basically it is designed as unary function, but if you enter two strings, then the total number of ones is 2a+b, where a and b are lengths of 1 and 2 strings respectively.

Code:

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

Simulating \(f_2(n)\) in the FGH

Enter two strings of ones and my program doubles the second string, first number of times.

Code:

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

\(f_2(n)\) exactly in FGH

As previous machine, but with one string.

Code:

0 _ * r 7
0 1 _ r 1
1 1 * r 1
1 _ * r 2
2 _ 1 l 3
2 1 1 r 2
3 _ * l 4
3 1 * l 3
4 1 * l 4
4 _ 1 r 0
5 1 * r 5
5 _ * r 6
6 _ * r 6
6 1 * l 6a
6a _ * r 7
7 _ _ l 8
7 1 _ r 8
8 1 * r 8
8 _ * r 9
9 _ 1 r 10
9 1 * r 9
10 _ 1 l 11
11 _ * l 12
11 1 * l 11
12 _ * r 13
12 1 * l 12
13 _ * l 14
13 1 _ r 8
14 _ * l 14
14 1 _ l 15
15 _ * l halt
15 1 * r 5

Other variant of \(f_2(n)\)

This variant keeps the gap between the number of iterations and resulting string.

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

\(f_3(n)\) exactly in FGH

When only seven ones entered, the total number of ones after halting will be larger than Poincaire recurrence time in the Planck times for the observable universe.

Code:

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

\(f_4(n)\) exactly in FGH

Enter n ones and TM returns number of ones greater or equal than \(2 \uparrow\uparrow\uparrow n\). For instance, entering merely 2 ones will return more than \(2 \uparrow\uparrow 2048\) ones.

Code:

0 _ * r 5
0 1 _ r 1
1 1 * r 1
1 _ * r 2
2 _ 1 l 3
2 1 * r 2
3 1 * l 3
3 _ * l 4
4 1 * l 4
4 _ 1 r 0
5 _ * r 10
5 1 _ r 6
6 1 * r 6
6 _ * r 7
7 _ 1 l 8
7 1 * r 7
8 1 * l 8
8 _ * l 9
9 1 * l 9
9 _ 1 r 5
10 _ * r 15
10 1 _ r 11
11 1 * r 11
11 _ * r 12
12 _ 1 l 13
12 1 * r 12
13 1 * l 13
13 _ * l 14
14 1 * l 14
14 _ 1 r 10
15 _ * r halt
15 1 _ r 16
16 1 * r 16
16 _ * r 17
17 _ 1 r 18
17 1 * r 17
18 _ 1 l 19
19 1 * l 19
19 _ * l 20
20 1 * l 21
20 _ * l 22
21 1 * l 21
21 _ * r 15
22 _ * l 22
22 1 _ l 23
23 1 * r 24
23 _ * l 26
24 _ * r 24
24 1 * l 25
25 _ * r 15
26 _ * l 26
26 1 _ l 27
27 _ * l 30
27 1 * r 28
28 _ * r 28
28 1 * l 29
29 _ * r 10
30 _ * l 30
30 1 _ l 31
31 _ * l halt
31 1 * r 32
32 _ * r 32
32 1 * l 33
33 _ * r 5

Note: the general pattern for \(f_m(n)\) and some lower bounds for \(\Sigma(n)\)

I've discovered the general method for constructing the TM that compute \(f_m(n)\). The table for \(f_m(n)\) \((m \geq 2)\) requires at most 9n-2 states and looks like that:

0 _ * r 5
0 1 _ r 1
1 1 * r 1
1 _ * r 2
2 _ 1 l 3
2 1 * r 2
3 1 * l 3
3 _ * l 4
4 1 * l 4
4 _ 1 r 0
T (transition table for TM for f_m-1(n) expect that in every rule, for states A ... B we replace it to A+5 ... B+5)
9m-6 _ * l 9m-6
9m-6 1 _ l 9m-5
9m-5 _ * l halt
9m-5 1 * r 9m-4
9m-4 _ * r 9m-4
9m-4 1 * l 9m-3
9m-3 _ * r 5

Therefore, I can state that table for \(f_m(n)\) would require 9n-2 states. For the \(\Sigma(n)\) condition, we need to start initially with the blank tape. Since \(f_m(1) = 2\) for every m, it is necessary to write at least two ones to start to perform the function. Hence, two additional states are required and thereby \(\Sigma(9n) \geq f_m(2)\) \((m \geq 2)\). This bound is weaker than Milton Green's one.

Also I can compare specific \(\Sigma(n)\) outputs with up-arrow notation:

\(\Sigma(18) \geq f_2(2) = 8\)

\(\Sigma(27) \geq f_3(2) = 2048\)

\(\Sigma(36) \geq f_4(2) > 2 \uparrow\uparrow 2048 > 2 \uparrow\uparrow\uparrow 3\)

\(\Sigma(45) \geq f_5(2) > 2 \uparrow\uparrow\uparrow (2 \uparrow\uparrow 2048) > 2 \uparrow\uparrow\uparrow\uparrow 3\)

\(\Sigma(54) \geq f_6(2) > 2 \uparrow^{5} 3\)

\(\Sigma(63) \geq f_7(2) > 2 \uparrow^{6} 3\)

In general:

\(\Sigma(9n) \geq f_m(2) > 2 \uparrow^{m-1} 3\)

Copy of string of ones

I found that it is possible using merely 5 states.

Code:

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

Square string of ones

Leaves \(n^2\) ones at the tape when n are written (in the form: n separated blocks of n's). Furthermore, it allows me to create \(f_\omega(n)\). Maybe this code can be optimized:

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

Square string of ones, n times

Input two strings: the first indicates the number of squarings, the second indicates the base.

0 1 * r 0
0 _ * r 1
1 _ * r halt
1 1 _ r 2
2 1 * r 2
2 _ * r 3
3 _ * r 4
4 _ 1 l 5
4 1 * r 4
5 _ * l 6
5 1 * l 5
6 _ * l 7
7 _ 1 r 8
7 1 * l 7
8 1 _ r 2
8 _ * l 16
9 _ * l 14
9 1 _ r 10
10 1 * r 10
10 _ * r 11
11 _ 1 l 12
11 1 1 r 11
12 _ * l 13
12 1 * l 12
13 1 * l 13
13 _ 1 r 9
14 1 * l 14
14 _ * l 15
15 _ * l 16
15 1 * l 14
16 _ * l 16
16 1 _ l 17
17 _ * r 23
17 1 * r 18
18 _ * r 18
18 1 * r 19
19 1 * r 19
19 _ * r 20
20 1 * r 19
20 _ * l 21
21 _ * l 22
22 1 * l 22
22 _ * r 9
23 _ * r 23
23 1 * * 24
24 _ * r 29
24 1 _ r 25
25 1 * r 25
25 _ * r 26
26 1 * r 26
26 _ 1 l 27
27 1 * l 27
27 _ * l 28
28 1 * l 28
28 _ * r 24
29 _ * r 30
29 1 * r 29
30 _ * l 33
30 1 * l 31
31 _ * l 32
32 1 * l 32
32 _ * r 24
33 _ * l 33
33 1 * l 34
34 1 * l 34
34 _ * l 35
35 _ * l 35
35 1 _ l 36
36 _ * l halt
36 1 * r 37
37 _ * r 37
37 1 * * 1

Division with integer result

(This version remains here because I want to discover its general behavior.)

Enter two strings and it computes their ratio if it is integer. If it is not integer, then it can either produces incorrect result or work infinitely (I believe it should be fixed using remainders).

Code:

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

Also challenging problem: determine when input leads to infinite looping and when not.

Fixed division

Now it works correctly with any positive integer values, computing ceil(a/b), where ceil(n) rounds up to the nearest integer.

Code:

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

Decimal-unary converter

Enter the decimal number and TM will return that number of ones.

Code:

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

Unary-decimal converter

Enter the number in unary and TM converts it in decimal.

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

More generalized converter

Converts a number from base-2 to the given base from 3 to 10. Syntax: write 2, then space, then number, then

0 _ * r 0
0 0 * r 0
0 1 * r 0
0 2 * r 1
1 _ * r 2
2 0 * r 2
2 1 * r 2
2 2 * r 2
2 3 * r 2
2 4 * r 2
2 5 * r 2
2 6 * r 2
2 7 * r 2
2 8 * r 2
2 9 * r 2
2 _ * l 3
3 _ * l 46
3 0 1 l 3
3 1 0 r 4
4 0 * r 4
4 1 * r 4
4 _ * r 5
; For base 3
5 3 * l 6
6 _ * l 7
7 0 * l 7
7 1 * l 7
7 _ * l 8
8 0 * l 9
8 1 * l 9
8 2 * l 9
9 _ * l 10
10 _ 1 r 0
10 0 1 r 0
10 1 2 r 0
10 2 0 l 10
; For base 4
5 4 * l 11
11 _ * l 12
12 0 * l 12
12 1 * l 12
12 _ * l 13
13 0 * l 14
13 1 * l 14
13 2 * l 14
13 3 * l 14
14 _ * l 15
15 _ 1 r 0
15 0 1 r 0
15 1 2 r 0
15 2 3 r 0
15 3 0 l 15
; For base 5
5 5 * l 16
16 _ * l 17
17 0 * l 17
17 1 * l 17
17 _ * l 18
18 0 * l 19
18 1 * l 19
18 2 * l 19
18 3 * l 19
18 4 * l 19
19 _ * l 20
20 _ 1 r 0
20 0 1 r 0
20 1 2 r 0
20 2 3 r 0
20 3 4 r 0
20 4 0 l 20
; For base 6
5 6 * l 21
21 _ * l 22
22 0 * l 22
22 1 * l 22
22 _ * l 23
23 0 * l 24
23 1 * l 24
23 2 * l 24
23 3 * l 24
23 4 * l 24
23 5 * l 24
24 _ * l 25
25 _ 1 r 0
25 0 1 r 0
25 1 2 r 0
25 2 3 r 0
25 3 4 r 0
25 4 5 r 0
25 5 0 l 25
; For base 7
5 7 * l 26
26 _ * l 27
27 0 * l 27
27 1 * l 27
27 _ * l 28
28 0 * l 29
28 1 * l 29
28 2 * l 29
28 3 * l 29
28 4 * l 29
28 5 * l 29
28 6 * l 29
29 _ * l 30
30 _ 1 r 0
30 0 1 r 0
30 1 2 r 0
30 2 3 r 0
30 3 4 r 0
30 4 5 r 0
30 5 6 r 0
30 6 0 l 30
; For base 8
5 8 * l 31
31 _ * l 32
32 0 * l 32
32 1 * l 32
32 _ * l 33
33 0 * l 34
33 1 * l 34
33 2 * l 34
33 3 * l 34
33 4 * l 34
33 5 * l 34
33 6 * l 34
33 7 * l 34
34 _ * l 35
35 _ 1 r 0
35 0 1 r 0
35 1 2 r 0
35 2 3 r 0
35 3 4 r 0
35 4 5 r 0
35 5 6 r 0
35 6 7 r 0
35 7 0 l 35
; For base 9
5 9 * l 36
36 _ * l 37
37 0 * l 37
37 1 * l 37
37 _ * l 38
38 0 * l 39
38 1 * l 39
38 2 * l 39
38 3 * l 39
38 4 * l 39
38 5 * l 39
38 6 * l 39
38 7 * l 39
38 8 * l 39
39 _ * l 40
40 _ 1 r 0
40 0 1 r 0
40 1 2 r 0
40 2 3 r 0
40 3 4 r 0
40 4 5 r 0
40 5 6 r 0
40 6 7 r 0
40 7 8 r 0
40 8 0 l 40
; For base 10
5 1 * l 41
41 _ * l 42
42 0 * l 42
42 1 * l 42
42 _ * l 43
43 0 * l 44
43 1 * l 44
43 2 * l 44
43 3 * l 44
43 4 * l 44
43 5 * l 44
43 6 * l 44
43 7 * l 44
43 8 * l 44
43 9 * l 44
44 _ * l 45
45 _ 1 r 0
45 0 1 r 0
45 1 2 r 0
45 2 3 r 0
45 3 4 r 0
45 4 5 r 0
45 5 6 r 0
45 6 7 r 0
45 7 8 r 0
45 8 9 r 0
45 9 0 l 45
46 2 _ r 47
47 _ * r 48
48 1 _ r 48
48 0 _ r 48
48 _ * r 49
49 0 _ r halt
49 1 _ r 49
49 3 _ r halt
49 4 _ r halt
49 5 _ r halt
49 6 _ r halt
49 7 _ r halt
49 8 _ r halt
49 9 _ r halt

String subsequence determiner

Determine whether the one string is a subsequence of another. It returns 1 if the subsequence operation is true, and none otherwise. It works only with 2-symbol alphabet for the second string and 1-symbol alphabet for the first string (I will try to improve it), and the syntax as follows:

  • Write first string and 1 at the end.
  • Immediately after it write second string and 1 at the end.

Code:

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

Improved string subsequence determiner

As previous: 2-symbol alphabet, but now it allows to have 2-symbol typed 1st string. Also you need to write "12" after the first string instead of "1". Symbol "2" is used to keep the ordering of strings. You can enter long strings to see how it works.

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

Multiplication of strings

Computes a*b, where a and b represented by string of ones separated by the one space.

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

Factorial

Computes \(n!\). It works also for 0! = 1.

0 _ 1 r halt
0 1 _ r 50
1 1 * r 1
1 _ * r 2
2 _ * r 3
3 _ 1 l 4
3 1 * r 3
4 _ * l 5
4 1 * l 4
5 _ * l 6
6 _ 1 r 7
6 1 * l 6
7 1 _ r 1
7 _ 2 l 8
8 2 * l 8
8 1 * l 8
8 _ * r 9
9 1 _ r 10
9 2 _ r halt
10 1 _ r 11
10 2 * r 40
11 1 * r 11
11 2 * r 11
11 _ * r 12
12 _ * r 12
12 1 * r 13
13 1 * r 13
13 _ * r 14
14 1 * r 14
14 _ 1 l 15
15 _ * l 16
15 1 * l 15
16 1 * l 16
16 _ * l 45
17 2 * l 17
17 1 * l 17
17 _ 1 r 10
18 _ * r 46
18 1 _ r 33
19 1 * r 19
19 _ * r 20
20 _ * l 25
20 1 * r 28
21 1 * r 21
21 _ * r 22
22 _ 1 l 23
22 1 * r 22
23 _ * l 24
23 1 * l 23
24 1 * l 24
24 _ 1 r 32
25 1 * l 25
25 _ * l 26
26 1 * l 25
26 _ * r 27
27 _ * r 18
28 1 * r 28
28 _ * r 29
29 1 * r 28
29 _ * l 30
30 _ * l 31
31 1 * l 31
31 _ * r 32
32 1 _ r 21
32 _ * l 25
33 _ * r 34
33 1 * r 19
34 _ * r halt
34 1 _ r 35
35 1 * r 35
35 _ 1 r 36
36 _ * r 37
36 1 * r 36
37 _ * l 41
37 1 * l 38
38 _ * l 39
39 1 * l 39
39 _ * r 34
40 _ * r 18
41 _ * l 42
42 1 * l 42
42 _ * l 43
43 _ * l 43
43 2 * l 44
44 1 * l 47
44 _ * r 9
45 _ * l 45
45 2 * l 17
46 _ * r 46
46 1 _ r 33
47 _ * r 49
47 1 * l 48
48 1 * l 48
48 _ * r 9
49 1 _ r 49
49 2 _ r halt
50 _ 1 l halt
50 1 * r 1

String breakdown

It breaks strings into blocks such that first block have first 2 letters of initial string, second 3 next letters, third 4 next letters, and so on. It is similar to breakdown that need for compute n(k), although there exist some sufficient difference. Nonetheless, the code:

0 _ * r 9
0 a _ r 1
1 a * r 1
1 b * r 1
1 _ * r 2
2 _ a l 3
2 1 * r 2
2 a * r 2
2 b * r 2
3 _ * l 4
3 1 * l 3
3 a * l 3
3 b * l 3
4 a * l 4
4 b * l 4
4 _ a r 0
0 b _ r 5
5 a * r 5
5 b * r 5
5 _ * r 6
6 _ b l 7
6 1 * r 6
6 a * r 6
6 b * r 6
7 a * l 7
7 b * l 7
7 _ * l 8
8 a * l 8
8 b * l 8
8 _ b r 0
9 _ * l 15
9 a _ r 11
9 b _ r 11
10 _ * l 15
11 a * r 11
11 b * r 11
11 _ * r 12
12 1 * r 12
12 _ 1 l 13
13 _ * l 14
13 1 * l 13
14 a * l 14
14 b * l 14
14 _ * r 9
15 _ * l 15
15 a * r 39
15 b * r 39
16 a * l 16
16 b * l 16
16 _ * l 17
17 _ 1 l 18
18 _ 1 r 19
19 1 * r 19
19 _ * l 20
20 _ * r 25
20 1 _ l 21
21 1 * l 21
21 _ * l 22
22 1 * l 22
22 _ 1 r 23
23 1 * r 23
23 _ * r 24
24 1 * r 24
24 _ 1 l 20
25 1 * r 25
25 _ * r 25
25 a * r 40
25 b * r 40
25 2 _ l 45
26 _ * l 26
26 1 * l 27
26 a * l 26
26 b * l 26
27 _ * r 28
27 1 * l 27
27 a * r 28
27 b * r 28
28 1 a r 32
28 b * r 28
29 _ * l 29
29 1 * l 30
29 a * l 29
29 b * l 29
30 _ * r 31
30 1 * l 30
30 a * l 30
30 b * l 30
31 a * r 31
31 b * r 31
31 1 b r 32
32 _ * r 33
32 1 * r 25
33 _ * r 33
33 a * r 34
33 b * r 34
33 2 _ r 43
34 a * r 34
34 b * r 34
34 _ * r 34
34 1 _ l 35
34 2 * r 34
35 _ * l 35
35 2 * l 36
36 b * l 36
36 a * l 36
36 _ * l 36
36 1 * l 37
37 1 * l 37
37 _ 1 r 38
38 1 * r 38
38 _ * l 20
39 _ 2 l 16
40 a * r 40
40 b * r 40
40 _ * r 40
40 2 * l 41
41 a * l 41
41 b * l 41
41 _ * r 42
42 a _ l 26
42 b _ l 29
42 2 _ r 43
43 _ * r 43
43 1 _ r 44
44 1 _ r 44
44 _ * l 45
45 _ * l 45
45 a * l 45
45 b * l 45
45 1 _ l 46
46 1 _ l 46
46 a _ l 46
46 b _ l 46
46 _ * l 47
47 _ * l halt
47 1 _ l 46

\(f_\omega(n)\) in FGH

It is my first non primitive recursive function. I hope that it works correctly now.

0 _ * r halt
0 1 _ r 1
1 1 * r 1
1 _ * r 2
2 _ * r 3
3 _ 1 l 4
3 1 * r 3
4 _ * l 5
4 1 * l 4
5 _ * l 6
6 _ 1 r 7
6 1 * l 6
7 1 _ r 1
7 _ * l 15
8 _ * l 13
8 1 _ r 9
9 1 * r 9
9 _ * r 10
10 _ 1 l 11
10 1 1 r 10
11 _ * l 12
11 1 * l 11
12 1 * l 12
12 _ 1 r 8
13 1 * l 13
13 _ * l 14
14 _ * l 15
14 1 * l 13
15 _ * l 15
15 1 _ l 16
16 _ * r 22
16 1 * r 17
17 _ * r 17
17 1 * r 18
18 1 * r 18
18 _ * r 19
19 1 * r 18
19 _ * l 20
20 _ * l 21
21 1 * l 21
21 _ * r 8
22 _ * r 22
22 1 * l 23
23 _ 2 r 24
24 1 * r 24
24 _ * r 25
25 _ * l 26
25 1 * r 24
26 _ * l 27
27 _ * r 28
27 1 * l 27
27 2 1 l halt
28 _ * l 34
28 1 _ r 29
29 1 * r 29
29 _ * r 30
30 1 * r 30
30 _ 1 r 31
31 _ 1 l 32
32 1 * l 32
32 _ * l 33
33 1 * l 33
33 _ * r 28
34 _ * l 34
34 1 _ l 35
35 _ * r 38
35 1 * r 36
35 2 _ l halt
36 _ * r 36
36 1 * l 37
37 _ * r 28
38 _ * r 38
38 1 * r 39
39 1 * r 39
39 _ * r 40
40 1 * r 39
40 _ * l 41
41 _ * l 42
42 1 * l 42
42 _ * r 43
43 _ * l 48
43 1 _ r 44
44 1 * r 44
44 _ * r 45
45 1 * r 45
45 _ 1 l 46
46 1 * l 46
46 _ * l 47
47 1 * l 47
47 _ 1 r 43
48 1 * l 48
48 _ * l 49
49 _ * l 50
49 1 * l 48
50 _ * l 50
50 1 _ l 51
51 _ * r 38
51 1 * r 52
52 _ * r 52
52 1 * r 24

\(f_{\omega+1}(n)\) in FGH

It is easy to make a function with expandal growth from it. Entering merely 65 ones and make this TM run can lead to the sequence of more than Graham's number ones.

0 _ * r 5
0 1 _ r 1
1 1 * r 1
1 _ * r 2
2 _ 1 l 3
2 1 * r 2
3 1 * l 3
3 _ * l 4
4 1 * l 4
4 _ 1 r 0
5 _ * r halt
5 1 _ r 6
6 1 * r 6
6 _ * r 7
7 _ * r 8
8 ^ _ r 58
8 _ * r 58
8 _ 1 l 9
8 1 * r 8
9 _ * l 10
9 1 * l 9
10 _ * l 11
11 _ 1 r 12
11 1 * l 11
12 1 _ r 6
12 _ * l 20
13 _ * l 18
13 1 _ r 14
14 1 * r 14
14 _ * r 15
15 _ 1 l 16
15 1 1 r 15
16 _ * l 17
16 1 * l 16
17 1 * l 17
17 _ 1 r 13
18 1 * l 18
18 _ * l 19
19 _ * l 20
19 1 * l 18
20 _ * l 20
20 1 _ l 21
21 _ * r 27
21 1 * r 22
22 _ * r 22
22 1 * r 23
23 1 * r 23
23 _ * r 24
24 1 * r 23
24 _ * l 25
25 _ * l 26
26 1 * l 26
26 _ * r 13
27 _ * r 27
27 1 * l 28
28 _ 2 r 29
29 1 * r 29
29 _ * r 30
30 _ * l 31
30 1 * r 29
31 _ * l 32
32 _ * r 33
32 1 * l 32
32 2 1 l 58
33 _ * l 39
33 1 _ r 34
34 1 * r 34
34 _ * r 35
35 1 * r 35
35 _ 1 r 36
36 _ 1 l 37
37 1 * l 37
37 _ * l 38
38 1 * l 38
38 _ * r 33
39 _ * l 39
39 1 _ l 40
40 _ * r 43
40 1 * r 41
40 2 _ l 58
41 _ * r 41
41 1 * l 42
42 _ * r 33
43 _ * r 43
43 1 * r 44
44 1 * r 44
44 _ * r 45
45 1 * r 44
45 _ * l 46
46 _ * l 47
47 1 * l 47
47 _ * r 48
48 _ * l 53
48 1 _ r 49
49 1 * r 49
49 _ * r 50
50 1 * r 50
50 _ 1 l 51
51 1 * l 51
51 _ * l 52
52 1 * l 52
52 _ 1 r 48
53 1 * l 53
53 _ * l 54
54 _ * l 55
54 1 * l 53
55 _ * l 55
55 1 _ l 56
56 _ * r 43
56 1 * r 57
57 _ * r 57
57 1 * r 29
58 _ * l 58
58 1 _ l 59
59 _ * l halt
59 1 * r 60
60 _ * r 60
60 1 * l 61
61 _ * r 5

Exponentiation

Computes \(a^b\), where a and b represented by the string of ones.

0 1 _ r 1
1 1 * r 1
1 ^ * r 1
1 _ * r 2
2 1 * r 2
2 _ 1 l 3
3 1 * l 3
3 _ * l 4
4 1 * l 4
4 ^ * l 4
4 _ * r 5
5 1 _ r 1
5 ^ _ r 6
6 1 * r 6
6 _ ^ l 7
7 1 * l 7
7 _ * r 8
8 _ * r 58
8 1 _ r 9
9 1 _ r 10
9 ^ _ l halt
10 1 * r 10
10 ^ * r 11
11 _ * l 59
11 1 _ r 12
11 x * l 16
12 1 * r 12
12 _ x r 13
12 x * r 13
13 _ 1 l 14
13 1 * r 13
14 x * l 15
14 1 * l 14
15 1 * l 15
15 _ 1 r 11
16 1 * l 16
16 x * l 16
16 ^ * l 17
17 1 * l 17
17 _ * r 18
18 1 _ r 19
18 ^ * r 22
19 1 * r 19
19 ^ * r 20
20 1 * r 20
20 x * r 20
20 _ * l 21
21 1 * l 21
21 x * r 11
22 1 * r 22
22 x * r 22
22 _ * l 23
23 1 * l 23
23 x * l 24
24 1 _ l 25
25 1 _ r 26
25 x _ r 60
25 ^ _ r 64
26 _ * r 26
26 x * r 27
27 1 * r 27
27 _ * r 28
28 1 * r 27
28 _ * l 29
29 _ * l 30
30 1 * l 30
30 x * r 31
30 _ * r 31
31 _ * l 36
31 1 _ r 32
32 1 * r 32
32 _ * r 33
33 _ 1 l 34
34 1 * l 34
34 _ * l 35
33 1 * r 33
35 1 * l 35
36 1 * l 36
36 _ * l 36
36 x * l 37
37 _ * l 37
37 1 _ r 26
37 x * r 38
37 ^ _ r 51
35 _ 1 r 31
38 _ * r 38
38 x * r 39
39 1 * r 39
39 _ * r 40
40 1 * l 41
40 _ * l 45
41 _ * l 42
42 1 * l 42
42 x * r 43
42 _ * r 43
43 1 _ r 44
44 1 * r 44
44 _ 1 r 39
45 _ x l 46
46 1 * l 46
46 _ * l 46
46 x _ r 47
47 _ * r 47
47 1 _ l 48
47 x _ l 50
48 _ * l 48
48 x * r 49
48 1 * r 49
49 _ 1 r 47
50 _ * l 50
50 1 * l 23
51 _ * r 51
51 x _ r 52
52 1 * r 52
52 _ * r 53
53 1 * l 54
53 _ * r halt
54 _ * l 55
55 1 * l 55
55 _ * r 56
56 1 _ r 57
57 1 * r 57
57 _ 1 r 52
58 ^ _ r 58
58 1 _ r 58
58 _ 1 r halt
59 ^ _ l 59
59 1 _ l 59
59 _ * l halt
60 _ * r 61
61 x _ r 61
61 1 _ r 61
61 _ * l 62
62 _ * l 62
62 1 _ l 63
63 x _ l 63
63 1 _ l 63
63 ^ 1 l halt
64 _ * r 64
64 x _ r 64
64 1 * r halt

Knuth's up-arrow notation

Computes \(a \uparrow^{c-2} b\) exactly, where a and b are string of ones, and c is given by string of +'s. Using +'s here is more logical than ^'s.

0 * * r 0
0 _ * l 1
1 1 * l 1
1 + * l 2
1 _ * l halt
2 1 * r 3
2 + * r 5
3 + 1 r 3
3 1 * r 3
3 _ * l 4
4 1 _ l 1
4 + _ r 4
4 _ 1 r halt
5 + * r 5
5 1 * r 5
5 _ * l 6
6 1 _ l 7
7 * * l 7
7 _ * l 8
8 1 * l 8
8 _ 1 r 9
9 1 * r 9
9 _ * r 10
10 * * r 10
10 _ * l 6
6 + * l 0a
;A-block
0a * * l 0a
0a _ * l 1a
1a 1 * l 1a
1a _ * r 2a
2a 1 _ r 3a
2a _ * r 14a
3a * * r 3a
3a _ * r 4a
4a * * r 4a
4a _ * l 5a
5a + _ l 6a
6a + * l 6a
6a 1 * l 7a
7a 1 * l 7a
7a * * r 8a
8a 1 _ r 9a
8a + _ r 11a
9a * * r 9a
9a _ 1 l 10a
10a * * l 10a
10a _ 1 r 8a
11a 1 * l 14a
11a + * r 12a
12a * * r 12a
12a _ + l 13a
13a * * l 13a
13a _ + r 8a
14a _ + r 15a
14a 1 _ r 14a
14a + _ r 4
15a * * r 15a
15a _ + l 16a
16a * * l 16a
16a _ * l 0b
;B-block
0b * * l 0b
0b _ * r 1b
1b _ * r 4b
1b 1 _ r 2b
2b 1 * r 2b
2b _ * r 3b
3b * * r 3b
3b _ * l 6a
4b * * r 4b
4b _ * l 5b
5b + _ l 5b
5b 1 _ l 6b
6b 1 _ l 6b
6b + _ l 7b
7b + _ l 7b
7b 1 * l 8b
8b * * l 8b
8b _ * r 0

Powers of two through decimal

Enter the number in decimal. Then TM will compute \(2^n\) in decimal and convert it into unary.

0 0 1 r halt
0 1 * l 0
0 2 * l 0
0 3 * l 0
0 4 * l 0
0 5 * l 0
0 6 * l 0
0 7 * l 0
0 8 * l 0
0 9 * l 0
0 _ | l 1
0 | * r 2
1 _ 1 r 0
2 0 * r 2
2 1 * r 2
2 2 * r 2
2 3 * r 2
2 4 * r 2
2 5 * r 2
2 6 * r 2
2 7 * r 2
2 8 * r 2
2 9 * r 2
2 _ * l 3
3 | _ r 8
3 0 9 l 3
3 1 0 l 4
3 2 1 l 4
3 3 2 l 4
3 4 3 l 4
3 5 4 l 4
3 6 5 l 4
3 7 6 l 4
3 8 7 l 4
3 9 8 l 4
4 0 * l 4
4 1 * l 4
4 2 * l 4
4 3 * l 4
4 4 * l 4
4 5 * l 4
4 6 * l 4
4 7 * l 4
4 8 * l 4
4 9 * l 4
4 | * l 5
5 0 * l 5
5 1 2 l 5
5 2 4 l 5
5 3 6 l 5
5 4 8 l 5
5 5 0 l 6
5 6 2 l 6
5 7 4 l 6
5 8 6 l 6
5 9 8 l 6
5 _ * r 7
6 0 1 l 5
6 _ 1 l 5
6 1 3 l 5
6 2 5 l 5
6 3 7 l 5
6 4 9 l 5
6 5 1 l 6
6 6 3 l 6
6 7 5 l 6
6 8 7 l 6
6 9 9 l 6
7 0 * r 7
7 1 * r 7
7 2 * r 7
7 3 * r 7
7 4 * r 7
7 5 * r 7
7 6 * r 7
7 7 * r 7
7 8 * r 7
7 9 * r 7
7 | * r 2
8 9 _ r 8
8 _ * l 9
9 0 * r 9
9 1 * r 9
9 2 * r 9
9 3 * r 9
9 4 * r 9
9 5 * r 9
9 6 * r 9
9 7 * r 9
9 8 * r 9
9 9 * r 9
9 _ * l 9a
9a _ * l 9a
9a 1 * * 10a
9a 2 * * 10a
9a 3 * * 10a
9a 4 * * 10a
9a 5 * * 10a
9a 6 * * 10a
9a 7 * * 10a
9a 8 * * 10a
9a 9 * * 10a
9a 0 * * 10a
10a 0 * r 10a
10a 1 * r 10a
10a 2 * r 10a
10a 3 * r 10a
10a 4 * r 10a
10a 5 * r 10a
10a 6 * r 10a
10a 7 * r 10a
10a 8 * r 10a
10a 9 * r 10a
10a _ * l 10
10 0 9 l 10
10 1 0 r 11
10 2 1 r 11
10 3 2 r 11
10 4 3 r 11
10 5 4 r 11
10 6 5 r 11
10 7 6 r 11
10 8 7 r 11
10 9 8 r 11
10 _ * r 14
11 _ * r 12
11 9 * r 11
12 _ 1 l 13
12 1 * r 12
13 _ * l 10
13 1 * l 13
14 9 _ r 14
14 _ * l halt

Square root

Here is my long variant. It calculates integer part of \(\sqrt{n}\), where n, of course, represented by a string of ones.

;Default block
0 _ * r halt
0 1 * l 1
1 _ * l 2
2 1 * l 2
2 _ 1 r 3
3 1 * r 3
3 _ * r 0e
;E-block (initial copying)
0e _ * l 0f
0e 1 _ r 1e
1e 1 * r 1e
1e _ * r 2e
2e _ 1 l 3e
2e 1 * r 2e
3e 1 * l 3e
3e _ * l 4e
4e 1 * l 4e
4e _ 1 r 0e
;A-block (start squaring)
0a _ * l 7a
0a 1 _ r 1a
1a 1 * r 1a
1a _ * r 2a
2a _ * r 3a
3a 1 * r 3a
3a _ 1 l 4a
4a _ * l 5a
4a 1 * l 4a
5a _ * l 6a
6a 1 * l 6a
6a _ 1 r 0a
7a 1 _ l 8a
7a _ * l halt
8a _ * r 22a
8a 1 * r 9a
9a _ * r 9a
9a 1 * r 10a
10a 1 * r 10a
10a _ * r 11a
11a 1 * r 10a
11a _ * l 12a
12a _ * l 13a
13a 1 * l 13a
13a _ * r 14a
14a _ * l 19a
14a 1 _ r 15a
15a 1 * r 15a
15a _ * r 16a
16a 1 * r 16a
16a _ 1 l 17a
17a 1 * l 17a
17a _ * l 18a
18a 1 * l 18a
18a _ 1 r 14a
19a 1 * l 19a
19a _ * l 20a
20a 1 * l 19a
20a _ * l 21a
21a _ * l 21a
21a 1 * * 7a
22a _ * r 22a
22a 1 * r 0b
;B-block (concatenating)
0b 1 * r 0b
0b _ * r 1b
1b 1 * l 2b
1b _ * l 0c
2b _ * l 3b
3b 1 * l 3b
3b _ * r 4b
4b 1 _ r 5b
5b 1 * r 5b
5b _ 1 r 0b
;C-block (pulling)
0c _ * l 0c
0c 1 * l 1c
1c 1 * l 1c
1c _ * l 2c
2c _ * l 2c
2c 1 * r 3c
3c _ * r 4c
4c _ 1 r 5c
5c _ * r 5c
5c 1 _ r 6c
6c 1 * l 7c
6c _ * l 0d
7c _ * l 7c
7c 1 * r 4c
;D-block (comparing)
0d _ * l 0d
0d 1 _ l 1d
1d 1 * l 1d
1d _ * l 2d
2d 1 * l 2d
2d _ * r 3d
3d 1 _ r 4d
3d _ * l 0i
4d 1 * r 4d
4d _ * r 5d
5d _ * l 0h
5d 1 * r 6d
6d _ * l 0d
6d 1 * r 6d
7d _ * l 8d
;F-block (copying-for-square)
0f 1 * l 0f
0f _ * l 1f
1f 1 * l 1f
1f _ * r 2f
2f _ * r 0g
2f 1 _ r 3f
3f 1 * r 3f
3f _ * r 4f
4f 1 * r 4f
4f _ * r 5f
5f 1 * r 5f
5f _ * r 6f
6f _ 1 l 7f
6f 1 * r 6f
7f _ * l 8f
7f 1 * l 7f
8f 1 * l 8f
8f _ * l 9f
9f 1 * l 9f
9f _ * l 10f
10f 1 * l 10f
10f _ 1 r 2f
;G-block (start for A-D blocks)
0g 1 * r 0g
0g _ * r 1g
1g 1 * r 1g
1g _ * r 0a
;H-block (incrementing the counter, since the comparison is true)
0h _ * l 1h
1h 1 _ l 1h
1h _ * l 2h
2h _ * l 2h
2h 1 * l 3h
3h 1 * l 3h
3h _ * r 0
;I-block (the comparison is false, so leave only counter)
0i _ * r 1i
1i _ * r 2i
2i 1 _ r 2i
2i _ * l 3i
3i _ * l 3i
3i 1 _ l 4i
4i 1 _ l 4i
4i _ * l 5i
5i 1 _ r halt

Divisibility test

Checks whether one number is dividable by another one. It leaves 1 if it is dividable and blank otherwise.

;Default block (copying the second string)
0 1 * r 0
0 _ * r 1
1 1 * r 1
1 _ * l 2
2 _ * l 9
2 1 _ l 3
3 1 * l 3
3 _ * l 4
4 1 * l 4
4 _ * l 5
5 1 * l 5
5 _ 1 r 6
6 _ * r 7
6 1 * r 6
7 1 * r 7
7 _ * r 8
8 1 * r 8
8 _ 1 l 2
9 1 * l 9
9 _ * r 0a
;A-block (preparing the first string)
0a _ * r 0b
0a 1 _ r 1a
1a 1 * r 1a
1a _ * r 2a
2a 1 * r 2a
2a _ * r 3a
3a 1 * r 3a
3a _ 1 l 4a
4a 1 * l 4a
4a _ * l 5a
5a 1 * l 5a
5a _ * l 6a
6a 1 * l 6a
6a _ 1 r 0a
;B-block (preparing the second string)
0b _ * r 0c
0b 1 _ r 1b
1b 1 * r 1b
1b _ * r 2b
2b 1 * r 2b
2b _ * r 3b
3b 1 * r 3b
3b _ 1 l 4b
4b _ * l 5b
4b 1 * l 4b
5b 1 * l 5b
5b _ * l 6b
6b 1 * l 6b
6b _ 1 r 0b
;C-block (checking the comparison)
0c _ * r 6c
0c 1 _ r 1c
1c 1 * r 1c
1c _ * r 2c
2c 1 * r 2c
2c _ * l 3c
3c _ * l 0f
3c 1 _ l 4c
4c 1 * l 4c
4c _ * l 5c
5c 1 * l 5c
5c _ * r 0c
6c 1 * * 0d
6c _ * l 0e
;D-block (the first number is not dividable by the second one, so we should leave nothing at the tape)
0d 1 _ r 0d
0d _ * l 1d
1d _ * l 1d
1d 1 _ l 2d
2d 1 _ l 2d
2d _ * l 3d
3d 1 _ l 3d
3d _ * l 4d
4d 1 _ l 4d
4d _ * l halt
;E-block (the first number is dividable by the second one, so we should leave 1 at the tape)
0e _ * l 0e
0e 1 _ l 1e
1e 1 _ l 1e
1e _ * l 2e
2e 1 _ l 2e
2e _ * l 3e
3e 1 _ l 3e
3e _ 1 l halt
;F-block (we can't conclude the divisibility now, increase the coefficient of the second number and iterate blocks A-C)
0f 1 _ l 0f
0f _ * l 1f
1f _ * l 1f
1f 1 * l 2f
2f 1 * l 2f
2f _ * l 3f
3f 1 * l 3f
3f _ * l 4f
4f 1 * l 4f
4f _ * r 5f
5f _ * r 0a
5f 1 _ r 6f
6f 1 * r 6f
6f _ * r 7f
7f 1 * r 7f
7f _ * r 8f
8f 1 * r 8f
8f _ 1 l 9f
9f 1 * l 9f
9f _ * l 10f
10f 1 * l 10f
10f _ * l 11f
11f 1 * l 11f
11f _ 1 r 5f

Primarily test

Very complicated primarily tester (112 states and 2 colors). Also it has very big time complexity (eleven has been verified to be prime only after more than 2 million steps).

;Default block
0 _ * r halt
0 1 * r 5
1 _ 1 l 2
2 _ 1 r 3
3 1 * r 4
4 1 * r 4
4 _ * r 0a
5 1 * r 6
5 _ * l 8
6 _ * l 7
6 1 * l 9
7 1 _ r halt
8 1 _ l halt
9 1 * l 9
9 _ * l 1
;A-block (copying the string)
0a _ * l 0b
0a 1 _ r 1a
1a 1 * r 1a
1a _ * r 2a
2a 1 * r 2a
2a _ 1 l 3a
3a _ * l 4a
3a 1 * l 3a
4a 1 * l 4a
4a _ 1 r 0a
;B-block (copying the counter and preparing to the divisibility test)
0b 1 * l 0b
0b _ * l 1b
1b 1 * l 1b
1b _ * r 2b
2b _ * r 11b
2b 1 _ r 3b
3b 1 * r 3b
3b _ * r 4b
4b 1 * r 4b
4b _ * r 5b
5b 1 * r 5b
5b _ * r 6b
6b 1 * r 6b
6b _ 1 l 7b
7b _ * l 8b
7b 1 * l 7b
8b 1 * l 8b
8b _ * l 9b
9b 1 * l 9b
9b _ * l 10b
10b 1 * l 10b
10b _ 1 r 2b
11b 1 * r 11b
11b _ * r 0aa
;AA-block (preparing the second string)
0aa _ * r 0ba
0aa 1 _ r 1aa
1aa 1 * r 1aa
1aa _ * r 2aa
2aa 1 * r 2aa
2aa _ * r 3aa
3aa 1 * r 3aa
3aa _ 1 l 4aa
4aa 1 * l 4aa
4aa _ * l 5aa
5aa 1 * l 5aa
5aa _ * l 6aa
6aa 1 * l 6aa
6aa _ 1 r 0aa
;BA-block (preparing the second string)
0ba _ * r 0ca
0ba 1 _ r 1ba
1ba 1 * r 1ba
1ba _ * r 2ba
2ba 1 * r 2ba
2ba _ * r 3ba
3ba 1 * r 3ba
3ba _ 1 l 4ba
4ba _ * l 5ba
4ba 1 * l 4ba
5ba 1 * l 5ba
5ba _ * l 6ba
6ba 1 * l 6ba
6ba _ 1 r 0ba
;CA-block (checking the comparison)
0ca _ * r 6ca
0ca 1 _ r 1ca
1ca 1 * r 1ca
1ca _ * r 2ca
2ca 1 * r 2ca
2ca _ * l 3ca
3ca _ * l 0fa
3ca 1 _ l 4ca
4ca 1 * l 4ca
4ca _ * l 5ca
5ca 1 * l 5ca
5ca _ * r 0ca
6ca 1 * * 0c
6ca _ * l 0g
;FA-block (we can't conclude the divisibility now, increase the coefficient of the second number and iterate blocks AA-CA)
0fa 1 _ l 0fa
0fa _ * l 1fa
1fa _ * l 1fa
1fa 1 * l 2fa
2fa 1 * l 2fa
2fa _ * l 3fa
3fa 1 * l 3fa
3fa _ * l 4fa
4fa 1 * l 4fa
4fa _ * l 5fa
5fa 1 * l 5fa
5fa _ * r 6fa
6fa _ * r 15fa
6fa 1 _ r 7fa
7fa 1 * r 7fa
7fa _ * r 8fa
8fa 1 * r 8fa
8fa _ * r 9fa
9fa 1 * r 9fa
9fa _ * r 10fa
10fa 1 * r 10fa
10fa _ 1 l 11fa
11fa 1 * l 11fa
11fa _ * l 12fa
12fa 1 * l 12fa
12fa _ * l 13fa
13fa 1 * l 13fa
13fa _ * l 14fa
14fa 1 * l 14fa
14fa _ 1 r 6fa
15fa 1 * r 15fa
15fa _ * r 0aa
;C-block (number is not dividable, so we should increase the counter)
0c 1 _ r 0c
0c _ * l 1c
1c _ * l 1c
1c 1 _ l 2c
2c _ * l 3c
2c 1 _ l 2c
3c 1 * l 3c
3c _ * l 4c
4c 1 * l 4c
4c _ * l 5c
5c 1 * l 5c
5c _ 1 r 0d
;D-block (copying input number to compare it with counter)
0d 1 * r 0d
0d _ * r 1d
1d 1 * r 1d
1d _ * l 2d
2d _ * l 0e
2d 1 _ l 3d
3d 1 * l 3d
3d _ * l 4d
4d 1 * l 4d
4d _ * l 5d
5d 1 * l 5d
5d _ 1 r 6d
6d _ * r 7d
6d 1 * r 6d
7d 1 * r 7d
7d _ * r 8d
8d 1 * r 8d
8d _ 1 l 2d
;E-block (copying counter in "memory" over the copy of input number)
0e _ * l 0f
0e 1 _ l 1e
1e 1 * l 1e
1e _ * l 2e
2e 1 * l 2e
2e _ * l 3e
3e 1 * l 3e
3e _ 1 r 4e
4e 1 * r 4e
4e _ * r 5e
5e 1 * r 5e
5e _ * r 6e
6e 1 * r 6e
6e _ 1 l 0e
;F-block (comparison between counter and input number)
0f 1 * l 0f
0f _ * r 1f
1f _ * l 0h
1f 1 _ r 2f
2f 1 * r 2f
2f _ * r 3f
3f 1 * r 3f
3f _ * l 4f
4f _ * l 0i
4f 1 _ l 5f
5f 1 * l 5f
5f _ * l 6f
6f 1 * l 6f
6f _ * r 1f
;G-block (divisor is found, so the input number is not a prime. Remove all strings from the tape)
0g _ * l 0g
0g 1 _ l 1g
1g 1 _ l 1g
1g _ * l 2g
2g 1 _ l 2g
2g _ * l 3g
3g 1 _ l 3g
3g _ * l 4g
4g 1 _ l 4g
4g _ * l halt
;H-block (we found that there are no divisors remain to verify, so just remove all strings and leave 1)
0h _ * l 0h
0h 1 _ l 1h
1h 1 _ l 1h
1h _ * r 2h
2h _ * r 2h
2h 1 _ r 3h
3h 1 _ r 3h
3h _ * r 4h
4h 1 _ r 4h
4h _ 1 r halt
;I-block (we found that there are some divisors still remain, so we pull the copy on the counter and repeat blocks A-C)
0i 1 _ l 0i
0i _ * l 1i
1i _ * l 1i
1i 1 _ r 2i
2i _ * r 2i
2i 1 * l 3i
3i _ * l 4i
4i _ 1 l 5i
5i _ * l 5i
5i 1 _ l 6i
6i 1 * r 7i
6i _ * r 8i
7i _ * r 7i
7i 1 * l 4i
8i _ * r 8i
8i 1 * l 9i
9i _ 1 r 4

4-color record for G

Firstly, I created TM that can handle any primitive recursive function using 11 states and 4 colors:

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

When the number of consecutive x's in the input grows, the growth rate of outputs (represented by non-blank characters) will be comparable to \(f_\omega(n)\). For example:

\(xx1 = 15 > 2*4\)

\(xxx1 > 2^4\)

\(xxxx1 > 2 \uparrow\uparrow 4\)

\(xxxxx1 > 2 \uparrow\uparrow\uparrow 4\)

This is related to the fact that at the very first section of the tape (before first x) doubling loop is being performed, the second section iterates that loop (the number of 1's after very first x can force outputs to grow exponentially), third iterates that loop, and so on.

Then I have going to make TM that can loop the number of x's, and thereby exhibits expandal growth rate (in order to trump G):

0 1 _ l 0
0 _ 1 r 0
0 x * l 1
0 y * r 11
1 1 * l 1
1 _ y r 2
2 1 * r 2
2 x * r 3
3 1 2 l 10
3 2 * r 3
3 x * l 4
3 y * r 11
3 _ * r halt
4 2 1 l 4
4 x 1 l 4
4 1 * l 4
4 y * l 5
5 x * l 5
5 1 * l 5
5 _ x l 6
6 _ 1 r 6
6 x * r 6
6 1 * r 6
6 y * r 7
7 1 * r 7
7 2 1 l 13
7 _ 1 l 0
7 x * r 8
7 y * l 12
8 _ * r halt
8 1 2 l 9
8 2 * r 8
8 x * l 4
8 y * r 11
9 x * l 9
9 1 * l 9
9 2 * l 9
9 y 1 l 9
9 _ 1 r 0
10 2 * l 10
10 1 * l 10
10 x * l 10
10 y _ r 0
11 2 * r 11
11 _ * r halt
11 1 2 l 12
12 1 * l 13
12 2 * l 12
12 y * l 7
13 x * l 13
13 1 x l 13
13 2 x l 13
13 y x l 13
13 _ * r 0

Which takes only 14 states to construct.

Input in the form _y111...111 (with n 1's) corresponds to growth rate on par with \(f_{\omega+1}(n)\). First few inputs are:

\(y = 2\)

\(y1 = 4\)

\(y11 = 6\)

\(y111 = 24\)

\(y1111 > 2 \uparrow^{17} 4 > \{3,2,1,2\}\)

\(y11111 > \{3,3,1,2\}\)

\(y111111 > \{3,4,1,2\}\)

\(y\underbrace{111\cdots 111}_{n} > \{3,n-2,1,2\}\)

Therefore, input _y111...111 (with 68 1's) leads to more than G non-zeros on the finished tape.

Then I used the best 2-state, 4-color BB-candidate. The tape after halting looks like that:

3222...2223 (2048 2's)
          ^

I can modify the ruleset so that tape would look as:

1xxx...xx11 (2047 x's)
        ^

Using one more state, we can transform this to that:

 y111...1111 (2049 x's)
^

Then I can just plug my previous TM to this string, obtaining more than \(\{3,2047,1,2\}\) non-zeros on the finisted tape. Strictly speaking, I have the proof that \(\Sigma(17,4)>\{3,2047,1,2\}\) Below is the complete ruleset:

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

New record holder for \(\Sigma(6,5)\)

First of all, I created this 3 state, 5 color Turing machine that able to deal with tetration:

0 1 _ l 0
0 _ 1 r 0
0 x 1 l 1
0 y x l 2
0 2 _ r halt
1 1 * l 1
1 _ 1 r 0
2 1 x l 2
2 _ x l 0

Again I applied the same trick: we can perform doubling with merely 1 state. With 2 states, we can create TM where x's here recurses doubling, and y's recurses x's. "2" is just the brake. So, writing input _xxx...xxx2 (n x's) gives \(> 2^n\) 1's, and inputting _yyy...yyy2 (n x's) gives \(> 2 \uparrow\uparrow n\) 1's.

To obtain quite large number of y's, we can use current 2 state, 5 color record holder TM. It turns out that its finished tape looks like:

14222...222 (over centillion 2's)
  ^

If we use x's instead of 2's and y's instead of 3's in rules:

1y222...222 (over centillion 2's)
  ^

Now we just change the halting rule and add some more:

1 y 1 r 2
2 2 y r 2
2 _ 2 l 2
2 y * l 2
2 1 y l 2
2 _ y l 3

This leads to:

_yyy...yyy2 (\(\approx 1.7*10^{352}\) y's)

Thus, when my TM above is applied, it can lead to the sequence with more than \(2 \uparrow\uparrow (1.7*10^{352})\) 1's. All work requires 6 states and 5 colors. Below is the complete transition table:

0 _ 1 r 1
0 1 2 l 0
0 2 1 r 0
0 x 2 l 1
0 y 2 l 0
1 _ _ l 0
1 1 2 r 1
1 2 x r 1
1 x y r 0
1 y * r 2
2 2 y r 2
2 _ 2 l 2
2 y * l 2
2 1 y l 3
3 1 _ l 3
3 _ 1 r 3
3 x 1 l 4
3 y x l 5
3 2 _ r halt
4 1 * l 4
4 _ 1 r 3
5 1 x l 5
5 _ x l 3

Steinhaus-Moser notation

To compute n in m-gon, use 4[111...111]111...111 (with m+3 and n 1's respectively)

0 * * r 0
0 _ * l 1
1 1 * l 1
1 ] * l 2
1 4 _ l halt
2 [ _ r 2
2 ] _ r 0e
2 1 * l 3
3 1 * l 3
3 [ _ r 4
4 * * r 4
4 _ [ l 5
5 * * l 5
5 _ [ r 6
6 1 _ r 7
6 ] _ r 9
7 * * r 7
7 _ 1 l 8
8 * * l 8
8 _ 1 r 6
9 4 * r 9
9 1 4 r 10
9 [ * r 0f
10 * * r 10
10 _ * l 11
11 1 ] l 12
12 * * l 12
12 _ ] l 3
;F-block
0f * * r 0f
0f _ * l 1f
1f 1 _ l 1f
1f [ _ l 2f
2f * * l 2f
2f _ * l 5f
2f 4 3 r 3f
3f * * r 3f
3f _ 1 l 4f
4f * * l 4f
4f 3 4 l 2f
5f 1 _ l 5f
5f [ _ r 5f
5f _ * r 5f
5f 4 _ r 6f
6f 4 _ r 6f
6f * * r 6f
6f _ * l 1
;E-block
0e _ * r halt
0e 1 _ r 1e
0e 2 * l 0d
1e 1 * r 1e
1e 2 * r 2e
1e _ 2 r 2e
2e _ 1 l 3e
2e 1 * r 2e
3e 2 * l 3e
3e 1 * l 3e
3e _ 1 r 0e
;D-block
0d 1 * l 0d
0d _ * r 1d
0d 2 * l 4d
1d 1 _ r 2d
1d 2 _ r 3d
2d 1 * r 2d
2d 2 * r 0e
3d _ * r halt
3d 1 _ r 3d
3d 2 _ l halt
4d 1 * l 4d
4d 2 * l 4d
4d _ * r 5d
5d 1 _ r 6d
5d 2 _ r 8d
6d 1 * r 6d
6d 2 * r 6d
6d _ * l 7d
7d 1 * l 7d
7d 2 * r 0e
8d 1 _ r 8d
8d 2 3 r 0c
;C-block
0c * * r 0c
0c _ 2 l 1c
1c 1 * l 1c
1c 2 * l 2c
1c 3 _ r 1b
2c 1 * l 2c
2c 2 * r 0a
2c 3 * r 0a
;A-block
0a 1 _ r 1a
0a 2 _ r 6a
1a 1 * r 1a
1a 2 * r 2a
2a 1 _ r 3a
2a 2 * l 5a
3a 1 * r 3a
3a 2 * r 3a
3a _ 1 l 4a
4a 1 * l 4a
4a 2 * l 4a
4a _ 1 r 2a
5a 1 * l 5a
5a 2 * l 5a
5a _ * r 0a
6a 1 _ r 6a
6a 2 _ r 0b
;B-block
0b _ * r 0b
0b 1 * r 1b
1b 2 _ l 3b
1b 1 * r 1b
1b _ * l 2b
2b 1 _ l 3b
3b 1 * l 3b
3b ] * r 0
3b _ 1 r 1b
3b 2 * r 4b
3b 3 _ r 5b
3b 4 _ l halt
4b 1 * r 4b
4b _ 1 r 0c
5b 1 * r 5b
5b _ 1 l 3b

Finite-indexed FGH

f111...111(111...111) (with m and n ones respectively corresponds to f_m(n))

0 * * r 0
0 _ * l 3
0 ( * r 1
1 f * r 0
1 1 * l 1
1 2 _ r 4
1 ( * l 2
2 1 * l 2
2 f _ r 0a
3 ) _ l 3
3 1 * l 3
3 2 _ l 3
3 _ * l halt
4 * * r 4
4 _ | l 5
5 * * l 5
5 _ * r 7f
;A-block
0a * * r 0a
0a _ | r 1a
1a _ f l 2a
2a * * l 2a
2a _ f r 3a
3a 1 _ r 4a
3a ( _ r 6a
3a ) _ r 8a
4a * * r 4a
4a _ 1 l 5a
5a * * l 5a
5a _ 1 r 3a
6a * * r 6a
6a _ ( l 7a
7a * * l 7a
7a _ ( r 3a
8a * * r 8a
8a _ ) l 9a
9a * * l 9a
9a ) _ l 10a
9a _ * l 11a
10a _ * l 10a
10a 1 _ l 10a
10a ( _ l 10a
10a ) _ l 10a
10a f _ r 0b
11a * _ l 11a
11a f 2 r 0b
;B-block
0b * * r 0b
0b | * r 1b
1b f _ r 2b
2b 1 f r 3b
2b ( 1 r 0g
3b 1 * r 3b
3b ( * r 4b
4b 1 _ l 5b
4b ) _ l 9b
5b * * l 5b
5b | * l 6b
6b 1 * l 6b
6b _ 1 r 7b
7b * * r 7b
7b ( * r 8b
8b 1 * r 8b
8b _ 1 r 4b
9b 1 _ l 9b
9b ( * l 0c
;C-block
0c * * l 0c
0c | * l 1c
1c 1 _ l 2c
2c 2 * l 3c
2c * * l 2c
2c f * l 3c
3c 1 * l 3c
3c _ 1 r 4c
3c f * l 3c
3c ( * l 3c
3c 2 1 r 4c
4c * * r 4c
4c _ * r 5c
5c _ * r 5c
5c 1 * r 6c
5c f * r 5c
5c | * l 7c
6c 1 * r 6c
6c _ 1 l 1c
6c ( * r 6c
6c | * l 7c
7c 1 * l 7c
7c _ * r 0d
;D-block
0d | * l 0e
0d 1 _ r 1d
1d * * r 1d
1d f _ r 2d
2d * * r 2d
2d _ f l 3d
3d * * l 3d
3d _ f r 4d
4d 1 _ r 5d
4d ( _ r 7d
5d * * r 5d
5d _ 1 l 6d
6d * * l 6d
6d _ 1 r 4d
7d * * r 7d
7d _ ( l 8d
8d * * l 8d
8d _ ( l 9d
9d * * l 9d
9d | * l 10d
10d 1 * l 10d
10d _ * r 0d
;E-block
0e 2 * l 1e
0e * * l 0e
0e f * l 1e
1e 1 * l 1e
1e _ | r 2e
1e ( * l 1e
1e f * l 1e
2e 1 _ r 3e
2e f * l 7e
2e 2 * l 7e
3e * * r 3e
3e | * r 4e
4e _ * r 5e
5e * * r 5e
5e _ 1 l 6e
6e * * l 6e
6e _ * l 0d
7e | _ l 7e
7e _ * r 7e
7e f * r 8e
7e 1 _ r 7e
7e 2 * r 8e
8e * * r 8e
8e | _ r 9e
9e _ * r 10e
10e * * r 10e
10e _ * l 0f
;F-block
0f _ * r 2f
0f * * l 0f
0f ( [ r 1f
1f * * r 1f
1f _ ) l 0f
2f * * r 2f
2f [ ( r 2f
2f _ * l 3f
3f ) * r 4f
4f _ ) r 5f
5f _ | l 6f
6f * * l 6f
6f _ * r 7f
7f _ * r 7f
7f 1 _ l 10f
7f f _ l 8f
7f ( _ l 12f
7f ) _ l 14f
7f | _ l 16f
8f _ * l 8f
8f 2 * r 9f
8f ( * r 9f
9f _ f r 7f
10f _ * l 10f
10f * * r 11f
11f _ 1 r 7f
12f _ * l 12f
12f * * r 13f
13f _ ( r 7f
14f _ * l 14f
14f * * r 15f
15f _ ) r 7f
16f _ * l 16f
16f ) * l 17f
17f * * l 17f
17f _ * r 0
;G-block
0g 1 * r 0g
0g ) * r 1g
1g _ | l 2g
2g * * l 2g
2g _ * l 3g
3g | _ r 7f

Hasse's algorithm

It is related to Collatz conjecture (but for single number). 
0 1 _ r 1
0 _ * l 2
1 _ * l 6
1 1 * r 0
2 1 _ l 3
3 1 * l 3
3 _ 1 l 4
4 _ * r 6
4 1 * r 5
5 1 * r 5
5 _ * l 2
6 _ 1 l 8
6 1 * r 7
7 1 * l 0
7 _ * r halt
8 1 * l 6
8 _ * r 9
9 _ * l 11
9 1 _ l 10
10 _ 1 l 11
11 _ 1 l 12
11 1 * l 11
12 1 * l 14
12 _ 1 r 13
13 1 * r 13
13 _ * r 9
14 1 * l 14
14 _ * r 0
For the number "27", it takes 164867015 steps.

Binary version

Binary version of it takes more colors and states, but the process becomes more compact and larger numbers can be allowed.

0 * * r 0
0 _ * l 1
1 0 _ l 1
1 1 * l 13
2 * * l 2
2 _ * r 3
3 _ * r 12
3 1 _ r 4
3 0 _ r 8
4 * * r 4
4 _ * r 5
5 _ 1 l 6
5 * * r 5
6 _ * l 7
6 * * l 6
7 * * l 7
7 _ 1 r 3
8 * * r 8
8 _ * r 9
9 * * r 9
9 _ 0 l 10
10 * * l 10
10 _ * l 11
11 * * l 11
11 _ 0 r 3
12 * * r 12
12 _ 1 * 0a
13 _ * l halt
13 * * l 2
;A-block
0a _ * r 5a
0a 1 0 l 1a
0a 0 1 l 0a
1a * * l 1a
1a _ * l 2a
2a _ 1 r 3a
2a 1 0 l 2a
2a 0 1 r 3a
3a * * r 3a
3a _ * r 4a
4a * * r 4a
4a _ * l 0a
5a 1 _ r 5a
5a _ * l 6a
6a _ * l 6a
6a * * * 1

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.