Mercurial > public > think_complexity

annotate TM.py @ 48:98eb01502cf5 tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Follow up to last commit. Re-orient the r-pentomino. Added progress display.
author Brian Neal <bgneal@gmail.com>
date Wed, 31 Jul 2013 20:37:12 -0500
parents 1804f09a7adb
children
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@45 82 # keep a history of head position & state tuples
bgneal@45 83 self.history = []
bgneal@45 84
bgneal@44 85 def loop(self, steps=1):
bgneal@44 86 """Attempts to execute the given number of steps. May exit early if the
bgneal@44 87 machine is already halted or halts during execution.
bgneal@44 88
bgneal@44 89 Returns the number of steps executed.
bgneal@44 90
bgneal@44 91 """
bgneal@44 92 actual = 0 # actual number of steps executed
bgneal@44 93 for i in xrange(steps):
bgneal@44 94 if self.state is None:
bgneal@44 95 break # machine has halted
bgneal@44 96 self.step()
bgneal@44 97 actual += 1
bgneal@44 98
bgneal@44 99 return actual
bgneal@44 100
bgneal@44 101 def step(self):
bgneal@44 102 """Executes one time step by computing the next row of the array."""
bgneal@45 103
bgneal@45 104 if len(self.history) == 0:
bgneal@45 105 # record initial head position & state
bgneal@45 106 self.history.append((self.head, self.state))
bgneal@45 107
bgneal@44 108 i = self.next - 1 # the previous state of the tape
bgneal@44 109 j = self.next # the row to write
bgneal@44 110 self.next += 1
bgneal@44 111
bgneal@44 112 a = self.array
bgneal@44 113 a[j, :] = a[i, :] # copy previous state of the tape to next row
bgneal@44 114
bgneal@44 115 # read the symbol on the tape at the head position
bgneal@44 116 symbol = a[j, self.head]
bgneal@44 117
bgneal@44 118 # see what we are supposed to do
bgneal@44 119 write_symbol, direction, next_state = self.actions[self.state, symbol]
bgneal@44 120
bgneal@44 121 # write a new symbol
bgneal@44 122 if write_symbol is not None:
bgneal@44 123 a[j, self.head] = write_symbol
bgneal@44 124
bgneal@44 125 # move the head
bgneal@44 126 if direction == LEFT:
bgneal@44 127 if self.head > 0:
bgneal@44 128 self.head -= 1
bgneal@44 129 else:
bgneal@44 130 raise TapeError("ran out tape moving LEFT")
bgneal@44 131 elif direction == RIGHT:
bgneal@44 132 if self.head < self.m - 1:
bgneal@44 133 self.head += 1
bgneal@44 134 else:
bgneal@44 135 raise TapeError("ran out tape moving RIGHT")
bgneal@44 136
bgneal@44 137 # change state
bgneal@44 138 self.state = next_state
bgneal@44 139
bgneal@45 140 # record what happened in our history
bgneal@45 141 self.history.append((self.head, self.state))
bgneal@45 142
bgneal@44 143 def get_array(self, start=0, end=None):
bgneal@44 144 """Gets a slice of columns from the array, with slice indices
bgneal@44 145 (start, end). Avoid copying if possible.
bgneal@44 146 """
bgneal@44 147 if start==0 and end==None:
bgneal@44 148 return self.array
bgneal@44 149 else:
bgneal@44 150 return self.array[:, start:end]
bgneal@44 151
bgneal@44 152
bgneal@44 153 if __name__ == '__main__':
bgneal@44 154 # Test the Turing Machine with the rules for a 3-state, 2 symbol busy beaver
bgneal@44 155
bgneal@44 156 A, B, C = range(3)
bgneal@44 157
bgneal@44 158 actions = {
bgneal@44 159 (A, 0): (1, RIGHT, B),
bgneal@44 160 (B, 0): (1, LEFT, A),
bgneal@44 161 (C, 0): (1, LEFT, B),
bgneal@44 162 (A, 1): (1, LEFT, C),
bgneal@44 163 (B, 1): (1, RIGHT, B),
bgneal@44 164 (C, 1): (1, RIGHT, None),
bgneal@44 165 }
bgneal@44 166
bgneal@44 167 n = 15
bgneal@44 168 m = 10
bgneal@44 169 tm = TM(A, actions, n, m)
bgneal@44 170
bgneal@44 171 count = tm.loop(n - 1)
bgneal@44 172 print count
bgneal@44 173 print tm.array
bgneal@45 174
bgneal@45 175 from TMDrawer import TMDrawer
bgneal@45 176
bgneal@45 177 tape_colors = {0: 0, 1: 40}
bgneal@45 178 state_colors = {
bgneal@45 179 A: 10,
bgneal@45 180 B: 20,
bgneal@45 181 C: 30,
bgneal@45 182 None: 40
bgneal@45 183 }
bgneal@45 184
bgneal@45 185 drawer = TMDrawer(tape_colors, state_colors, cmap='spectral')
bgneal@45 186 drawer.draw(tm)
bgneal@45 187 drawer.show()