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