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 day-to-day basis are decidedly unpoetic.

```
"""
Deterministic Turing Machine
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
This is a turing machine written in python. This code closely follows code from
chapter 5 of the book _Understanding Computation_ by Tom Stuart.
This is basically a Finite State Machine with a tape.
"""
import collections
LEFT = 'left'
RIGHT = 'right'
BLANK = '_'
Rule = collections.namedtuple('Rule', [
'state',
'head',
'next_state',
'write',
'move'])
def rule_applies(rule, state, tape):
"""Determine whether a rule applies to a state."""
correct_state = rule.state == state
correct_read = rule.head == tape.head
return correct_state and correct_read
def follow_rule(rule, state, tape):
"""Follows the current rule."""
if rule_applies(rule, state, tape):
state = rule.next_state
tape.middle = rule.write
tape.move(rule.move)
return rule, state, tape
class Tape(object):
"""Represents the tape in a turing machine."""
def __init__(self, left=None, middle=None, right=None, blank=BLANK):
"""Initialize and show initial state."""
self.left = left or []
self.right = right or []
self.middle = middle
if self.middle is None:
self.middle = blank
self.blank = blank
def move_right(self):
"""Move tape one unit right, add blanks as needed."""
self.left = self.left + [self.middle]
if self.right:
self.middle = self.right.pop(0)
else:
self.middle = self.blank
def move_left(self):
"""Move tape one unit left, add blanks as needed."""
self.right = [self.middle] + self.right
if self.left:
self.middle = self.left.pop()
else:
self.middle = self.blank
@property
def head(self):
return str(self.middle)
def move(self, direction):
"""Move tape left or right."""
if not direction in [LEFT, RIGHT]:
raise RuntimeError('Unrecognized direction "%s"' % direction)
if direction == LEFT:
return self.move_left()
if direction == RIGHT:
return self.move_right()
def __repr__(self):
"""Tape state with current head in parens, like _12(3)4."""
out = '{}({}){}'.format(
''.join(map(str, self.left)),
self.middle,
''.join(map(str, self.right)))
return out
class DeterministicTuringMachine(object):
"""This is a turing machine."""
def __init__(self, state, tape, accept_states, rules):
"""
Initialize machine
:state: - integer - that represents the current state of the machine
:tape: - Tape - the machine's tape
:accept_states: - [integer] - represents states when the machine has
exited successfully
:rules: - [Rule] - list of rules for the machine to follow
"""
self.state = state
self.tape = tape
self.accept_states = accept_states
self.rules = rules
@property
def accepting(self):
return self.state in self.accept_states
@property
def stuck(self):
"""Stuck when we have no next rule."""
return not self.next_rule
@property
def working(self):
"""Working when not done and we still have rules to apply."""
return not (self.accepting or self.stuck)
@property
def next_rule(self):
"""Get next rule."""
rules = self._find_rules()
if rules:
return rules[0]
return rules
def _find_rules(self):
"""Find a rules we can apply."""
applicable_rules = [rule for rule in self.rules
if rule_applies(rule, self.state, self.tape)]
return applicable_rules
def step(self):
"""Apply any rules we can find."""
_, self.state, self.tape = follow_rule(
self.next_rule, self.state, self.tape)
def run(self):
while self.working:
self.step()
```

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 right-most 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.

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 once-again over a `1`

, the same rule will be followed again:

Calling the `run`

method of the machine will continue to follow the defined rules until state `3`

is reached:

Turing machines are magic, I guess is what I’m saying.

Another rather poetic way of understanding low-level computing: https://tomorrowcorporation.com/humanresourcemachine

It’s a game where you automate your way through menial tasks in the mail room at a mega corporation. The catch: you have to use something resembling assembly language to implement the automation. It’s fun and challenging.

Comment by mmodell — Tue 2017-07-04 03:53:51 AM

Ah, you’ve mentioned this before! It does look pretty cool. I’ve played World of Goo which looks to be by the same folks and really enjoyed it