FANDOM


Here a hardy machines up to \(\omega 2\).

Turing Machines

\(H_1(n)\) machine

0 1 * r 0
0 _ 1 l 1
1 1 1 l 1
1 _ _ r halt

\(H_2(n)\) machine

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

\(H_3(n)\) machine

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

\(H_4(n)\) machine

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

\(H_m(n)\) machine

0 1 * r 0
0 _ 1 l 1
1 1 1 l 1
1 _ _ r 2
T for H_{m-1}(n), A and B replace A+2 and B+2, if m = 1, the 2*m state turn a halt state.

\(H_\omega(n)\) machine

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

\(H_{\omega+1}(n)\) machine

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

So omega+2 machine is n*2+4, omega+3 = n*2+8. In general, omega+m = n*2+m*2.

\(H_{\omega+m}(n)\) machine

0 1 * r 0
0 _ 1 l 1
1 1 1 l 1
1 _ _ r 2
T for H_(omega+m-1)(n), A and B replace A+2 and B+2, if m = 1, the 2*m state turn a H_omega(n) machine.

\(H_{\omega 2}(n)\) machine

For states 4 and 5, 2 states change to f_w(n) turing.

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.