FANDOM


My works

(coming soon?)

Works based on other people's ones

A 48 state, 3 symbol machine

Here, I'll introduce a Turing machine, based on LittlePeng9's Kirby-Paris hydra game machine and the 3-state, 3-symbol record holder.

This is the record holder for 3-state, 3-symbol Turing machines:

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

Just before the machine halts, the tape looks like this:

 12222...2222

where there are 374,676,381 2's, and the head is placed on the blank on the immediate left of 1, and on state 2.

I modified the record holder machine:

0 _ ) r 1
0 ( ) l 2
0 ) ( l 0
1 _ _ l 0
1 ( ) l 1
1 ) ( r 1
2 _ ( r halt
2 ( ) r 2
2 ) ) r 0

The tape when the machine halts looks like this:

()(((...(((

where there are 374,676,381 ('s, and the head is placed on the ) symbol.


I also proved that on the Kirby-Paris hydra game machine, when the input is

( (((...((( (where there are N ('s, excluding the leftmost one)

the number of ('s the machine leaving on the tape is larger than

\[f_{\varepsilon_0}(n-3)\]

using FGH (I won't go into the details).


Combining all of these, we have this Turing machine:

0   _ ) r bb1
0   ( ) l bb2
0   ) ( l 0
bb1 _ _ l 0
bb1 ( ) l bb1
bb1 ) ( r bb1
bb2 _ ( r 0a
bb2 ( ) r bb2
bb2 ) ) r 0

0a ) _ r 1
0a * * r 0a
0a _ _ r 1
1 * * r 1
1 _ _ l 2
2 * _ l 2
2 ( _ r 5

3 _ _ r 4
4 ( ( r 4'
4 ) _ r 27
4' * * r 4'
4' _ _ r 2

5 _ ) r 6
6 * * r 6
6 _ _ r 7
7 ) ) r 7
7 _ ) l 8
8 ) ) l 8
8 _ _ l 9
9 * * l 9
9 _ _ l 10
10 ) _ r 5
10 ( _ r 11
10 _ ( r 3
11 _ ( r 12
12 * * r 12
12 _ _ r 13
13 ) ) r 13
13 _ _ l 14
14 ) _ l 15
15 ) ) l 8
15 _ _ l 16

16 * * l 16
16 _ _ l 17
17 * * l 17
17 _ _ l 18
18 ( ( l 18
18 ) ( r 19
18 _ ( r 19
19 ( ) r 20
19 _ _ r 22
20 ( ( r 20
20 _ _ r 21
21 * * r 21
21 _ _ r c0

c0 ( _ l (1
c0 ) _ l )1
c0 _ ( r c3
(1 _ ( r (2
(2 _ _ r (3
(3 * * r (3
(3 _ _ r (4
(4 * * r (4
(4 _ ( l c1
)1 _ ) r )2
)2 _ _ r )3
)3 * * r )3
)3 _ _ r )4
)4 * * r )4
)4 _ ) l c1
c1 * * l c1
c1 _ _ l c2
c2 * * l c2
c2 _ _ r c0
c3 ( ( r c3
c3 ) ) l c4
c4 ( ) r c5
c5 ) ) r c5
c5 ( ( l c6
c5 _ _ l c7
c6 ) ( r c3
c7 ) _ l 16

22 * * r 22
22 _ _ r 23
23 * * r 23
23 _ _ l 24
24 ) _ l 25
25 ) ) l 25
25 ( ) l 26
26 ) ( l 25
26 ( ( l 26
26 _ ( r 1

27 _ _ r 27
27 ) _ l halt

Since this machine uses 48 states and 3 symbols, we have proven that

\[\Sigma(48,3) > f_{\varepsilon_0}(374676381-3) = f_{\varepsilon_0}(374676378)\]

which is larger than a goppatoth.

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.