FANDOM


For each state and each color there are 2 directions possible, 2 colors to choose and 3 states to go.

Beacause there are 3 states (0, 1 and L) with each 2 colors, this gives 126 = 2,985,984 machines.

Eliminate the most trivial

If we restrict to machines with one halting command, we get 6 places for that halting command, and then 25 possibilities for the other states to go. Further, the direction and the new color of the halting state doesn't matter. This gives 25 * 25 * 25 * 6 = 196,608 machines.

Other eliminations (case 0.0)

We calculate further form the 196,608 machines form above.

When the halting command is at the first state and the space, it halts after one step. This are 32,768 machines, or a sixth of the total.

Other eliminations (case 0.1)

Halting in two steps

0 _ 1 l 0 
0 1 halt

This are 4,096 machines.

Halting in three steps

0 _ 1 r 1 
0 1 halt
1 _ # l 0

This are 1,024 machines.

0 _ _ l 1
0 1 halt 
1 _ 1 l 0

This are 512 machines.

0 _ 1 l 1
0 1 halt 
1 1 1 l 0

This are 512 machines.

Halting in four steps

0 _ _ l 1 
0 1 halt
1 _ 1 l 1 
1 1 1 l 0

This are 64 machines.

0 _ 1 l 1 
0 1 halt 
1 _ 1 l 0
1 1 _ l 1

This are 64 machines.

0 _ 1 r 1 
0 1 halt 
1 _ # l 1 
1 1 1 l 0

This are 128 machines.

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

This are 64 machines.

Halting in five steps

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

This are 64 machines.

0 _ 1 l 1 
0 1 halt 
1 _ # r 0
1 1 _ r 0

This are 128 machines.

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

This are 64 machines.

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

This are 512 machines.

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

This are 64 machines.

Halting in six steps

0 _ _ r 1 
0 1 halt 
1 _ 1 l 0 
1 1 # l 1

This are 128 machines.

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

This are 64 machines.

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

This are 64 machines.

Halting in seven steps

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

This are 64 machines.

Halting in ten steps

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

This are 64 machines.

Halting in \(\omega+1\) steps

0 _ _ # 0 
0 1 halt
L _ 1 l 0

This are 1,024 machines.

0 _ 1 r 0 
0 1 halt
L 1 # r 0

This are 1,024 machines.

0 _ 1 r 0 
0 1 halt
L 1 1 l 0

This are 512 machines.

0 _ _ # 1 
0 1 halt 
1 _ _ # # 
L _ 1 l 0

This are 512 machines.

0 _ _ # 1 
0 1 halt 
1 _ 1 r # 
L 1 1 l 0

This are 256 machines.

0 _ _ # 1 
0 1 halt 
1 _ 1 r # 
L 1 # r 0

This are 512 machines.

0 _ 1 r 1 
0 1 halt 
1 _ # r # 
L 1 1 l 0

This are 256 machines.

0 _ 1 r 1 
0 1 halt 
1 _ 1 r # 
L 1 # r 0

This are 256 machines.

0 _ 1 l 1 
0 1 halt 
1 _ _ # 1
1 1 _ r 0
L _ 1 l 0

This are 16 machines.

0 _ 1 l 1 
0 1 halt 
1 _ 1 r 1
1 1 _ r 0
L 1 1 l 0

This are 8 machines.

0 _ 1 l 1 
0 1 halt 
1 _ 1 r 1
1 1 _ r 0
L 1 # r 0

This are 16 machines.

0 _ 1 l 1 
0 1 halt 
1 1 _ l 0
L 1 1 l 0

This are 64 machines.

Halting in \(\omega+2\) steps

0 _ _ l 0 
0 1 halt
L _ 1 r 0

This are 512 machines.

0 _ _ r 0 
0 1 halt
1 _ # l 0
L _ 1 r 1

This are 128 machines.

0 _ 1 r 0 
0 1 halt
1 1 # l 0
L 1 1 r 1

This are 128 machines.

0 _ 1 r 0 
0 1 halt
L 1 _ l 0

This are 512 machines.

0 _ 1 r 1 
0 1 halt 
1 _ 1 r 1

This are 512 machines.

Total of (0.1) machines

Steps Number of machines found All non-trivial machines?
2 4,096 yes
3 2,048
4 320
5 832
6 256
7 64
10 64
\(\omega+1\) 4,456
\(\omega+2\) 1,792

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.