--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/TM.py	Wed Jan 16 21:44:02 2013 -0600
@@ -0,0 +1,162 @@
+"""Chapter 6, exercise 4 in Allen Downey's Think Complexity book.
+
+The goal of this exercise is to implement a Turing machine.
+See http://en.wikipedia.org/wiki/Turing_machine.
+
+1. Start with a copy of CA.py named TM.py. Add attributes to represent the
+   location of the head, the action table and the state register.
+
+2. Override step to implement a Turing machine update.
+
+3. For the action table, use the rules for a 3-state busy beaver.
+
+"""
+import numpy
+
+# Tape head direction constants; None is also a legitimate value to indicate
+# no movement:
+
+LEFT, RIGHT = range(2)
+
+
+class TapeError(Exception):
+    """Raised when the tape head goes out of our array bounds."""
+    pass
+
+
+class TM(object):
+    """
+    A Turing Machine based upon the cellular automaton (CA.py) in Think
+    Complexity.
+
+    The tape is divided into cells where each cell can contain a symbol from
+    a finite alphabet. We use unsigned 8-bit integers, where 0 is the special
+    blank symbol.
+    The tape head can read & write symbols onto the tape at its current
+    position. The tape head can be moved according to the action table.
+    A state register stores the machine's current state. A state value of None
+    indicates the machine should halt.
+    An action table controls how the machine operates. Each entry in the table
+    is of the form:
+        (state, input) => (write_symbol, direction, new_state)
+
+    where:
+        state: current machine state
+        input: current symbol under the machine's tape head
+        write_symbol: the symbol to write onto the tape; None means don't write
+            anything
+        direction: the direction to move the head; can be either LEFT, RIGHT, or
+            None to indicate no movement.
+        next_state: the new state to transition to
+
+    """
+    def __init__(self, init_state, actions, n=100, m=50):
+        """Parameters:
+
+        init_state : the initial state of the machine
+
+        actions : the action table dictionary:
+            the keys are of the form (state, input)
+            the values are a tuple of the form (write_symbol, direction,
+            next_state)
+
+        n : the number of rows in the numpy array
+        m : the number of columns in the numpy array
+
+        The caller is free to intialize the first row in the array and/or move
+        the head prior to calling loop() or step(). Otherwise the tape will be
+        all blanks and the head placed in the middle.
+
+        """
+        # We use a numpy array to store the state of the tape at each step.
+        self.n = n
+        self.m = m
+        self.array = numpy.zeros((n, m), dtype=numpy.int8)
+
+        # the head is initially in the center of the first row
+        self.next = 1               # the next row to update
+        self.head = m / 2           # head position
+        self.actions = actions      # action table
+        self.state = init_state     # state
+
+    def loop(self, steps=1):
+        """Attempts to execute the given number of steps. May exit early if the
+        machine is already halted or halts during execution.
+
+        Returns the number of steps executed.
+
+        """
+        actual = 0      # actual number of steps executed
+        for i in xrange(steps):
+            if self.state is None:
+                break       # machine has halted
+            self.step()
+            actual += 1
+
+        return actual
+
+    def step(self):
+        """Executes one time step by computing the next row of the array."""
+        i = self.next - 1   # the previous state of the tape
+        j = self.next       # the row to write
+        self.next += 1
+
+        a = self.array
+        a[j, :] = a[i, :]   # copy previous state of the tape to next row
+
+        # read the symbol on the tape at the head position
+        symbol = a[j, self.head]
+
+        # see what we are supposed to do
+        write_symbol, direction, next_state = self.actions[self.state, symbol]
+
+        # write a new symbol
+        if write_symbol is not None:
+            a[j, self.head] = write_symbol
+
+        # move the head
+        if direction == LEFT:
+            if self.head > 0:
+                self.head -= 1
+            else:
+                raise TapeError("ran out tape moving LEFT")
+        elif direction == RIGHT:
+            if self.head < self.m - 1:
+                self.head += 1
+            else:
+                raise TapeError("ran out tape moving RIGHT")
+
+        # change state
+        self.state = next_state
+
+    def get_array(self, start=0, end=None):
+        """Gets a slice of columns from the array, with slice indices
+        (start, end).  Avoid copying if possible.
+        """
+        if start==0 and end==None:
+            return self.array
+        else:
+            return self.array[:, start:end]
+
+
+if __name__ == '__main__':
+    # Test the Turing Machine with the rules for a 3-state, 2 symbol busy beaver
+
+    A, B, C = range(3)
+
+    actions = {
+        (A, 0): (1, RIGHT, B),
+        (B, 0): (1, LEFT, A),
+        (C, 0): (1, LEFT, B),
+        (A, 1): (1, LEFT, C),
+        (B, 1): (1, RIGHT, B),
+        (C, 1): (1, RIGHT, None),
+    }
+
+    n = 15
+    m = 10
+    tm = TM(A, actions, n, m)
+
+    count = tm.loop(n - 1)
+    print count
+    print tm.array