FANDOM

10,837 Pages

Here are some of my Turing machines.

Hardy Hierarchy

Here are my Hardy Hierarchy machines. n|a=H_a(n), where n is a string of ones. w=$$\omega$$.

Up to H_w^2

Ordinals are connected by addition by placing them consecutively. Accepts 1's and w's.

0 * * r 0
0 _ _ l 1
1 1 _ l 2
1 | _ l halt
1 w _ l 3
2 * * l 2
2 _ 1 r 0
3 * * l 3
3 i 1 r 4
3 _ _ r 4
4 1 i r 5
4 | | r 0
5 * * r 5
5 _ 1 l 3


Slightly quickened version

Here H_0(n)=n+1, H_a+1(n)=H_a(n+1), H_a(n)=H_a[n+1](n+1).

0 * * r 0
0 _ _ l 1
1 1 _ l 2
1 | 1 l halt
1 w 1 l 3
2 * * l 2
2 _ 1 r 0
3 * * l 3
3 i 1 r 4
3 _ 1 r 4
4 1 i r 5
4 | | r 0
5 * * r 5
5 _ 1 l 5


Weird version

I haven't looked completely at everything here, but from what I can see: H_0(n)=n+2, H_a+1(n)=?, H_a(n)=H_a[n+3](n+2).

0 * * r 0
0 _ 1 l 1
1 1 _ l 2
1 | 1 l halt
1 w 1 l 3
2 * * l 2
2 _ 1 r 0
3 * * l 3
3 i 1 r 4
3 _ 1 r 4
4 1 i r 5
4 | | r 0
5 * * r 5
5 _ 1 l 3


Up to H_w^w

Ordinals are connected by +'s (addition) and x's (multiplication). Accepts w's and 1's.

0 * * r 0
0 _ _ l 1
1 w _ l 2
1 * _ l 1
1 | _ l halt
1 1 1 l 3
2 * * l 2
2 _ _ r 3w
2 i 1 r 3w
3w 1 i r 4w
3w | | r 0
4w * * r 4w
4w _ 1 l 2
3 1 1 l 3
3 * * r 4+
3 x x r pp4x
pp4x 1 1 r p4x
p4x _ _ l del1
p4x * * r 4x
4+ * * r 4+
4+ _ _ l 5+
5+ 1 _ l 6+
6+ * * l 6+
6+ _ 1 r 0
4x * * r 4x
4x _ _ l 5x
5x 1 + l 6x
6x 1 i l 6x
6x x x l 7x
7x * * l 7x
7x + + r 8x
7x | | r 8x
7x l 1 r 8x
8x i 1 r 8x
8x 1 l r 9i
8x w m r 9w
8x x X r 9x
8x + + r 0
9i * * r 9i
9i _ 1 l 7x
9w * * r 9w
9w _ w l 10x
9x * * r 9x
9x _ x l 10x
10x * * l 10x
10x X x r 8x
10x m w r 8x
del1 1 _ l 1


15 state 2 color up to H_w^2

Here "n a b c d ... f"=H_a+b+c+d...+f(n) where n is a string of ones and every other letter is either a single 1 (representing a single 1) or two consecutive ones (representing omega).

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


Coming soon!

FGH

n|a|b|c...y|z=f_a(f_b(f_c(...f_y(f_z(n)))...)), where n is a string of ones. Consecutive ordinals are connected by addition. Accepts 1's and w's.

Up to f_w^2(n)

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


If we make f_a(n)=f_a[n+1](n), then we can actually save 1 state.

Quickened Version

Here f_a(n)=f_a[n+1](n).

0 * * r 0
0 | | r 1
0 _ _ l halt
1 * * r 1
1 _ _ l 2
2 | _ l 3
2 w _ l 4
2 1 | l 7
3 * * l 3
3 _ 1 r 0
4 * * l 4
4 _ _ r 5
4 i 1 r 5
5 1 i r 6
5 | | l 0
6 * * r 6
6 _ 1 l 4
7 * * l 7
7 _ _ r 9
7 i 1 r 9
9 1 i r 10
9 | | r 18
10 * * r 10
10 _ _ l 11
11 | | l 12
12 * * l 12
12 | | r 13
13 w W r 14
13 1 l r 15
13 | | r 16
14 * * r 14
14 _ w l 17
15 * * r 15
15 _ 1 l 17
16 * * r 16
16 _ | l 7
17 * * l 17
17 W w r 13
17 l 1 r 13
18 * * r 18
18 _ _ l 19
19 | _ l 2


Removed states 8 and 20.

Almost done!

Coming soon!

Coming soon!

Single number Collatz Conjecture=

Posting in a second ;)