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:

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.

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.