Mercurial > public > think_complexity

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