Below is a Turing machine implementation based on the example in Understanding Computation by Tom Stuart. The Turing machine is an entertaining thought exercise that makes computer science feel a bit like poetry. Most things I learn on about computers on a daytoday basis are decidedly unpoetic.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 

This machine contains objects for a tape (Tape
), rules for a machine to follow (Rule
), and an object representing the state of the Turing machine itself (DeterministicTuringMachine
).
Incrementing binary numbers
Given the appropriate set of rules, this machine can perform general computing tasks. In the book, the rules for incrementing a binary number are used as an example.
We start with the number 10111
(A.K.A, 23), which we’d like to increment by 1 to get 11000
(A.K.A., 24). To begin we set the tape with the number we’d like to increment with the read head of the tape resting on rightmost digit of the binary number:
# Tape looks like: 1011(1)
# Where () represents the read/write head
t = Tape(left=[1,0,1,1], middle=1)
This machine will have three available machine “states” that help to define the rules for the Turing machine to follow. When the machine is in a particular state, and encounters a particular condition (i.e., the read head is over a particular number) it will follow a particular rule – that is, it will write either a 1
or a 0
, move the read head either LEFT
or RIGHT
, and, possibly, change machine state. These rules are based on machine state in combination with a read condition.
The machine will start in state 1
. When the machine enters into one of the accept_states
, the machine will stop processing. The only accept_state for this machine is 3
.
# Availale states in this example are 1, 2, 3
initial_state = 1
m = DeterministicTuringMachine(
state=initial_state, tape=t, accept_states=[3], rules=[
# if the state is 1 and the read head is ... etc
Rule(state=1, head='0', next_state=2, write='1', move=RIGHT),
Rule(state=1, head='1', next_state=1, write='0', move=LEFT),
Rule(state=1, head=BLANK, next_state=2, write='1', move=RIGHT),
# if the state is 2 and the read head is ... etc
Rule(state=2, head='0', next_state=2, write='0', move=RIGHT),
Rule(state=2, head='1', next_state=2, write='1', move=RIGHT),
Rule(state=2, head=BLANK, next_state=3, write=BLANK, move=LEFT)
]
)
If we call the step
method of the state machine we can trace how it follows rules.
>>> m.tape
1011(1)
>>> m.step()
>>> print(m.state)
1
>>> print(m.tape)
101(1)0
Since it was in state 1
and the read head was over a 1
it followed rule Rule(state=1, head='1', next_state=1, write='0', move=LEFT)
– it wrote 0
in its current location, it moved the read head LEFT
, and stayed in the 1
state. Since the state is still 1
and the read head is onceagain over a 1
, the same rule will be followed again:
>>> m.tape
101(1)0
>>> m.step()
>>> print(m.state)
1
>>> print(m.tape)
10(1)00
Calling the run
method of the machine will continue to follow the defined rules until state 3
is reached:
>>> m.run()
>>> print(m.state)
3
>>> print(m.tape)
1100(0)_
Turing machines are magic, I guess is what I’m saying.