Mercurial > public > think_complexity

annotate TM.py @ 44:362d4ec7e794

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Got a first draft Turing Machine working for chapter 6, exercise 4. Next I have to figure out how to draw it with a TMDrawer class.
author Brian Neal <bgneal@gmail.com>
date Wed, 16 Jan 2013 21:44:02 -0600
parents
children 1804f09a7adb
rev   line source
bgneal@44 1 """Chapter 6, exercise 4 in Allen Downey's Think Complexity book.
bgneal@44 2
bgneal@44 3 The goal of this exercise is to implement a Turing machine.
bgneal@44 4 See http://en.wikipedia.org/wiki/Turing_machine.
bgneal@44 5
bgneal@44 6 1. Start with a copy of CA.py named TM.py. Add attributes to represent the
bgneal@44 7 location of the head, the action table and the state register.
bgneal@44 8
bgneal@44 9 2. Override step to implement a Turing machine update.
bgneal@44 10
bgneal@44 11 3. For the action table, use the rules for a 3-state busy beaver.
bgneal@44 12
bgneal@44 13 """
bgneal@44 14 import numpy
bgneal@44 15
bgneal@44 16 # Tape head direction constants; None is also a legitimate value to indicate
bgneal@44 17 # no movement:
bgneal@44 18
bgneal@44 19 LEFT, RIGHT = range(2)
bgneal@44 20
bgneal@44 21
bgneal@44 22 class TapeError(Exception):
bgneal@44 23 """Raised when the tape head goes out of our array bounds."""
bgneal@44 24 pass
bgneal@44 25
bgneal@44 26
bgneal@44 27 class TM(object):
bgneal@44 28 """
bgneal@44 29 A Turing Machine based upon the cellular automaton (CA.py) in Think
bgneal@44 30 Complexity.
bgneal@44 31
bgneal@44 32 The tape is divided into cells where each cell can contain a symbol from
bgneal@44 33 a finite alphabet. We use unsigned 8-bit integers, where 0 is the special
bgneal@44 34 blank symbol.
bgneal@44 35 The tape head can read & write symbols onto the tape at its current
bgneal@44 36 position. The tape head can be moved according to the action table.
bgneal@44 37 A state register stores the machine's current state. A state value of None
bgneal@44 38 indicates the machine should halt.
bgneal@44 39 An action table controls how the machine operates. Each entry in the table
bgneal@44 40 is of the form:
bgneal@44 41 (state, input) => (write_symbol, direction, new_state)
bgneal@44 42
bgneal@44 43 where:
bgneal@44 44 state: current machine state
bgneal@44 45 input: current symbol under the machine's tape head
bgneal@44 46 write_symbol: the symbol to write onto the tape; None means don't write
bgneal@44 47 anything
bgneal@44 48 direction: the direction to move the head; can be either LEFT, RIGHT, or
bgneal@44 49 None to indicate no movement.
bgneal@44 50 next_state: the new state to transition to
bgneal@44 51
bgneal@44 52 """
bgneal@44 53 def __init__(self, init_state, actions, n=100, m=50):
bgneal@44 54 """Parameters:
bgneal@44 55
bgneal@44 56 init_state : the initial state of the machine
bgneal@44 57
bgneal@44 58 actions : the action table dictionary:
bgneal@44 59 the keys are of the form (state, input)
bgneal@44 60 the values are a tuple of the form (write_symbol, direction,
bgneal@44 61 next_state)
bgneal@44 62
bgneal@44 63 n : the number of rows in the numpy array
bgneal@44 64 m : the number of columns in the numpy array
bgneal@44 65
bgneal@44 66 The caller is free to intialize the first row in the array and/or move
bgneal@44 67 the head prior to calling loop() or step(). Otherwise the tape will be
bgneal@44 68 all blanks and the head placed in the middle.
bgneal@44 69
bgneal@44 70 """
bgneal@44 71 # We use a numpy array to store the state of the tape at each step.
bgneal@44 72 self.n = n
bgneal@44 73 self.m = m
bgneal@44 74 self.array = numpy.zeros((n, m), dtype=numpy.int8)
bgneal@44 75
bgneal@44 76 # the head is initially in the center of the first row
bgneal@44 77 self.next = 1 # the next row to update
bgneal@44 78 self.head = m / 2 # head position
bgneal@44 79 self.actions = actions # action table
bgneal@44 80 self.state = init_state # state
bgneal@44 81
bgneal@44 82 def loop(self, steps=1):
bgneal@44 83 """Attempts to execute the given number of steps. May exit early if the
bgneal@44 84 machine is already halted or halts during execution.
bgneal@44 85
bgneal@44 86 Returns the number of steps executed.
bgneal@44 87
bgneal@44 88 """
bgneal@44 89 actual = 0 # actual number of steps executed
bgneal@44 90 for i in xrange(steps):
bgneal@44 91 if self.state is None:
bgneal@44 92 break # machine has halted
bgneal@44 93 self.step()
bgneal@44 94 actual += 1
bgneal@44 95
bgneal@44 96 return actual
bgneal@44 97
bgneal@44 98 def step(self):
bgneal@44 99 """Executes one time step by computing the next row of the array."""
bgneal@44 100 i = self.next - 1 # the previous state of the tape
bgneal@44 101 j = self.next # the row to write
bgneal@44 102 self.next += 1
bgneal@44 103
bgneal@44 104 a = self.array
bgneal@44 105 a[j, :] = a[i, :] # copy previous state of the tape to next row
bgneal@44 106
bgneal@44 107 # read the symbol on the tape at the head position
bgneal@44 108 symbol = a[j, self.head]
bgneal@44 109
bgneal@44 110 # see what we are supposed to do
bgneal@44 111 write_symbol, direction, next_state = self.actions[self.state, symbol]
bgneal@44 112
bgneal@44 113 # write a new symbol
bgneal@44 114 if write_symbol is not None:
bgneal@44 115 a[j, self.head] = write_symbol
bgneal@44 116
bgneal@44 117 # move the head
bgneal@44 118 if direction == LEFT:
bgneal@44 119 if self.head > 0:
bgneal@44 120 self.head -= 1
bgneal@44 121 else:
bgneal@44 122 raise TapeError("ran out tape moving LEFT")
bgneal@44 123 elif direction == RIGHT:
bgneal@44 124 if self.head < self.m - 1:
bgneal@44 125 self.head += 1
bgneal@44 126 else:
bgneal@44 127 raise TapeError("ran out tape moving RIGHT")
bgneal@44 128
bgneal@44 129 # change state
bgneal@44 130 self.state = next_state
bgneal@44 131
bgneal@44 132 def get_array(self, start=0, end=None):
bgneal@44 133 """Gets a slice of columns from the array, with slice indices
bgneal@44 134 (start, end). Avoid copying if possible.
bgneal@44 135 """
bgneal@44 136 if start==0 and end==None:
bgneal@44 137 return self.array
bgneal@44 138 else:
bgneal@44 139 return self.array[:, start:end]
bgneal@44 140
bgneal@44 141
bgneal@44 142 if __name__ == '__main__':
bgneal@44 143 # Test the Turing Machine with the rules for a 3-state, 2 symbol busy beaver
bgneal@44 144
bgneal@44 145 A, B, C = range(3)
bgneal@44 146
bgneal@44 147 actions = {
bgneal@44 148 (A, 0): (1, RIGHT, B),
bgneal@44 149 (B, 0): (1, LEFT, A),
bgneal@44 150 (C, 0): (1, LEFT, B),
bgneal@44 151 (A, 1): (1, LEFT, C),
bgneal@44 152 (B, 1): (1, RIGHT, B),
bgneal@44 153 (C, 1): (1, RIGHT, None),
bgneal@44 154 }
bgneal@44 155
bgneal@44 156 n = 15
bgneal@44 157 m = 10
bgneal@44 158 tm = TM(A, actions, n, m)
bgneal@44 159
bgneal@44 160 count = tm.loop(n - 1)
bgneal@44 161 print count
bgneal@44 162 print tm.array