FANDOM

10,843 Pages

Here I want to propose how to give any Turing machine a corresponding binary relation R. Of course, a subsets of set of all relations are sets of partial orders, total orders and, most importantly, well orders. Thus we have alternative to Kleene's O correspondence of ordinals to machines.

Definition

Let us have any fixed Turing machine M. Corresponding relation R is defined on $$\mathbb{N}^2$$ as follows: xRy iff machine M halts on input 1x_1y.

Examples

$$\omega$$

$$\omega$$ is certainly simpliest one, as it is induced by standard natural number order >.

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


$$\omega+1$$

This one is first one defining nonstandard order > such that 2<3<4<...<1, so 1 is the only transfinite element.

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


(I'm sure this machine can be made with less states, for example by defining < instead of >, but I wish to keep direction of order consistent.)

$$\omega2$$

This machine defines order > such that 1<3<5<7<...<2<4<6<8<..., so we have $$\omega$$ transfinite numbers.

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