|
bgneal@45
|
1 """Chapter 6, exercise 4 in Allen Downey's Think Complexity book.
|
|
bgneal@45
|
2
|
|
bgneal@45
|
3 The goal of this exercise is to implement a Turing machine.
|
|
bgneal@45
|
4 See http://en.wikipedia.org/wiki/Turing_machine.
|
|
bgneal@45
|
5
|
|
bgneal@45
|
6 4. Write a class named TMDrawer that generates an image that represents the
|
|
bgneal@45
|
7 state of the tape and the position and state of the head. For one example of
|
|
bgneal@45
|
8 what that might look like, see
|
|
bgneal@45
|
9 http://mathworld.wolfram.com/TuringMachine.html.
|
|
bgneal@45
|
10
|
|
bgneal@45
|
11 """
|
|
bgneal@45
|
12 import matplotlib.pyplot as pyplot
|
|
bgneal@45
|
13 import numpy
|
|
bgneal@45
|
14
|
|
bgneal@45
|
15 from CADrawer import Drawer
|
|
bgneal@45
|
16
|
|
bgneal@45
|
17
|
|
bgneal@45
|
18 class TMDrawer(Drawer):
|
|
bgneal@45
|
19 """Implementation of Drawer using matplotlib for Turing Machines.
|
|
bgneal@45
|
20
|
|
bgneal@45
|
21 We visualize the tape and machine head/state by drawing the tape state as
|
|
bgneal@45
|
22 a row, then adding a row underneath that for the head & state. The tape head
|
|
bgneal@45
|
23 is drawn as a solid square whose color represents the state.
|
|
bgneal@45
|
24
|
|
bgneal@45
|
25 """
|
|
bgneal@45
|
26 def __init__(self, tape_colors, state_colors, cmap=None):
|
|
bgneal@45
|
27 self.tape_colors = tape_colors
|
|
bgneal@45
|
28 self.state_colors = state_colors
|
|
bgneal@45
|
29 self.cmap = cmap if cmap else 'spectral'
|
|
bgneal@45
|
30
|
|
bgneal@45
|
31 def draw(self, tm, start=0, end=None):
|
|
bgneal@45
|
32 """Draws the TM using pyplot.pcolor."""
|
|
bgneal@45
|
33 tape = tm.get_array(start, end)
|
|
bgneal@45
|
34 rows, cols = tape.shape
|
|
bgneal@45
|
35
|
|
bgneal@45
|
36 # create a new array that has twice as many rows
|
|
bgneal@45
|
37 steps = rows
|
|
bgneal@45
|
38 rows *= 2
|
|
bgneal@45
|
39 a = numpy.zeros((rows, cols), dtype=numpy.int8)
|
|
bgneal@45
|
40
|
|
bgneal@45
|
41 # copy the tape state into the array at every other row
|
|
bgneal@45
|
42 for i in xrange(steps):
|
|
bgneal@45
|
43 for j in xrange(cols):
|
|
bgneal@45
|
44 #a[n, j] = self.tape_colors[tape[i, j]]
|
|
bgneal@45
|
45 c = self.tape_colors[tape[i, j]]
|
|
bgneal@45
|
46 a[i * 2, j] = c
|
|
bgneal@45
|
47
|
|
bgneal@45
|
48 # copy the head position & state into every other row
|
|
bgneal@45
|
49 n = 1
|
|
bgneal@45
|
50 for pos, state in tm.history:
|
|
bgneal@45
|
51 a[n, pos] = self.state_colors[state]
|
|
bgneal@45
|
52 n += 2
|
|
bgneal@45
|
53
|
|
bgneal@45
|
54 # flipud puts the first row at the top;
|
|
bgneal@45
|
55 pyplot.pcolor(numpy.flipud(a), cmap=self.cmap)
|
|
bgneal@45
|
56 pyplot.axis([0, cols, 0, rows])
|
|
bgneal@45
|
57 pyplot.colorbar()
|
|
bgneal@45
|
58
|
|
bgneal@45
|
59 # empty lists draw no ticks
|
|
bgneal@45
|
60 pyplot.xticks([])
|
|
bgneal@45
|
61 pyplot.yticks([])
|
|
bgneal@45
|
62
|
|
bgneal@45
|
63 def show(self):
|
|
bgneal@45
|
64 """display the pseudocolor representation of the CA"""
|
|
bgneal@45
|
65 pyplot.show()
|
|
bgneal@45
|
66
|
|
bgneal@45
|
67 def save(self, filename='tm.png'):
|
|
bgneal@45
|
68 """save the pseudocolor representation of the TM in (filename)."""
|
|
bgneal@45
|
69 pyplot.savefig(filename)
|
|
bgneal@45
|
70
|
