Work is currently focused on state machines, so one night I got interested in Turing machines.
Turing machines aren’t really machines at all, more like a hypothetical model of a computer. You would almost never build a physical one - but they’re easy to simulate and despite their simplicity, can be fascinating. Theoretically, they can implement ANY computer algorithm.
(Quick plug for The Diamond Age which features 11 castles which are all Turing machines … wait, what ?!)
They read an infinite tape of 1s and 0s, and can move left or right on the tape; read what’s written on the tape; and update it. A machine is essentially a set of states, where the state number, and the read value are effectively a key, and lead to a particular behaviour : write something to the tape, move left or right, and change to a new state.
There are a couple of variations - some will write blanks (not just 0s or 1s); some have a tape that may be blank rather than all 0s to start; and sometimes there is a ‘stay’ option rather than move left or right.
And there is the idea of a halt state - you move to this and stop.
Simple example
In my notation …
0: 0->1,R,1, 1->1,L,-1; 1: 0->0,L,0, 1->0,L,0;
How to read this :
- anything before a colon is a state : this machine has two states, 0 and 1
- anything before an arrow -> is a read value
- a read value will have a comma separated list of 3 instructions : write value, direction, next state
- a state will have a space separted list of read values and end in a semi colon
- -1 is the halt state
So if this machine is in state 0 :
- if it reads a 0, it will write a 1, move Right, and move to state 1;
- if it reads a 1, it will write a 1 (back again), move Left, and halt
And if this machine is in state 1 :
- if it reads a 0, it will write a 0, move Left, and move to state 0;
- if it reads a 1, it will do the same as read value 0.
We start with a tape which is all 0s, in state 0. We read a 0, which means we write a 1, move Right, and move to state 1; now in state 1, we read another 0, write a 0, move Left, and move to state 0 again; but now we read a 1 (written just now), which means we it will write a 1, move Left, and halt.
2 steps, and the tape ends up as 0100 starting at index -1, which is where the machine ends up
Busy beavers
Busy Beavers take this idea further, to try and build a machine that produces the most output.
I’ve written a program to start exploring the possible Turing machine space.
With 2 states, 2 tape values and 2 directions I have 12 possible combinations.
There are 4 keys (state and read value combinations) which with 12 combinations means 20736 possibilities (Uh oh.)
Making those 20736 attempts, I found 2872 useful machines - ones that move more than once.
The best ran for 6 steps and produced a tape length of 4;
0: 0->1,R,1 1->0,L,1; 1: 0->1,L,0 1->0,L,-1
With 3 states, 2 tape values and 2 directions I have 16 possible combinations.
There are 6 keys which with 16 combinations means 1.6777216E7 attempts
16777216 attempts made and found 3377536 useful machines.
The best : 21 iterations and tape length 5;
0: 0->1,L,2 1->0,L,-1; 1: 0->1,R,1 1->1,R,0; 2: 0->1,R,2 1->0,L,1;
With 4 states, 2 tape values and 2 directions I have 20 possible combinations.
There are 8 keys which with 20 combinations means 2.56E10 attempts
Tt’s been running all day - 2.5 billion machines.
The best so far : 84 iterations and tape length 13;
0: 0->1,R,2 1->1,L,3; 1: 0->1,L,1 1->1,L,0; 2: 0->0,L,1 1->0,R,1; 3: 0->0,L,-1 1->0,L,0;
done i 84 : t 0101111101111
0 _________0___
1 _________1___
2 _________10__
3 _________10__
4 ________110__
5 ________100__
6 ________101__
7 ________111__
8 ________111__
9 _______1111__
10 _______1011__
11 _______1011__
12 _______1111__
13 _______1101__
14 _______1101__
15 _______1111__
16 _______1110__
17 _______11101_
18 _______11111_
19 _______11111_
20 _______11111_
21 _______01111_
22 ______101111_
23 ______101111_
24 ______101111_
25 _____1101111_
26 _____1001111_
27 _____1011111_
28 _____1111111_
29 _____1111111_
30 ____11111111_
31 ____10111111_
32 ____10111111_
33 ____11111111_
34 ____11011111_
35 ____11011111_
36 ____11111111_
37 ____11101111_
38 ____11101111_
39 ____11111111_
40 ____11110111_
41 ____11110111_
42 ____11111111_
43 ____11111011_
44 ____11111011_
45 ____11111111_
46 ____11111101_
47 ____11111101_
48 ____11111111_
49 ____11111110_
50 ____111111101
51 ____111111111
52 ____111111111
53 ____111111111
54 ____111101111
55 ____111101111
56 ____110101111
57 ____110101111
58 ____010101111
59 ___1010101111
60 ___1010101111
61 ___1010101111
62 __11010101111
63 __10010101111
64 __10110101111
65 __11110101111
66 __11110101111
67 _111110101111
68 _101110101111
69 _101110101111
70 _111110101111
71 _110110101111
72 _110110101111
73 _111110101111
74 _111010101111
75 _111010101111
76 _111110101111
77 _111100101111
78 _111101101111
79 _111111101111
80 _111111101111
81 _111111101111
82 _101111101111
83 _101111101111
84 0101111101111
Completed after 84 and tape 0101111101111