Mercurial > public > think_complexity

comparison TM.py @ 45:1804f09a7adb

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Chapter 6, exercise 4, part 4. A Turing Machine drawer.
author Brian Neal <bgneal@gmail.com>
date Sat, 19 Jan 2013 14:17:12 -0600
parents 362d4ec7e794
children
comparison
equal deleted inserted replaced
44:362d4ec7e794 45:1804f09a7adb
77 self.next = 1 # the next row to update 77 self.next = 1 # the next row to update
78 self.head = m / 2 # head position 78 self.head = m / 2 # head position
79 self.actions = actions # action table 79 self.actions = actions # action table
80 self.state = init_state # state 80 self.state = init_state # state
81 81
82 # keep a history of head position & state tuples
83 self.history = []
84
82 def loop(self, steps=1): 85 def loop(self, steps=1):
83 """Attempts to execute the given number of steps. May exit early if the 86 """Attempts to execute the given number of steps. May exit early if the
84 machine is already halted or halts during execution. 87 machine is already halted or halts during execution.
85 88
86 Returns the number of steps executed. 89 Returns the number of steps executed.
95 98
96 return actual 99 return actual
97 100
98 def step(self): 101 def step(self):
99 """Executes one time step by computing the next row of the array.""" 102 """Executes one time step by computing the next row of the array."""
103
104 if len(self.history) == 0:
105 # record initial head position & state
106 self.history.append((self.head, self.state))
107
100 i = self.next - 1 # the previous state of the tape 108 i = self.next - 1 # the previous state of the tape
101 j = self.next # the row to write 109 j = self.next # the row to write
102 self.next += 1 110 self.next += 1
103 111
104 a = self.array 112 a = self.array
127 raise TapeError("ran out tape moving RIGHT") 135 raise TapeError("ran out tape moving RIGHT")
128 136
129 # change state 137 # change state
130 self.state = next_state 138 self.state = next_state
131 139
140 # record what happened in our history
141 self.history.append((self.head, self.state))
142
132 def get_array(self, start=0, end=None): 143 def get_array(self, start=0, end=None):
133 """Gets a slice of columns from the array, with slice indices 144 """Gets a slice of columns from the array, with slice indices
134 (start, end). Avoid copying if possible. 145 (start, end). Avoid copying if possible.
135 """ 146 """
136 if start==0 and end==None: 147 if start==0 and end==None:
158 tm = TM(A, actions, n, m) 169 tm = TM(A, actions, n, m)
159 170
160 count = tm.loop(n - 1) 171 count = tm.loop(n - 1)
161 print count 172 print count
162 print tm.array 173 print tm.array
174
175 from TMDrawer import TMDrawer
176
177 tape_colors = {0: 0, 1: 40}
178 state_colors = {
179 A: 10,
180 B: 20,
181 C: 30,
182 None: 40
183 }
184
185 drawer = TMDrawer(tape_colors, state_colors, cmap='spectral')
186 drawer.draw(tm)
187 drawer.show()