Jeremy Bowers said:
I had to think about it, it's an interesting, and I'm going to tentatively
disagree, because of the statement/expression dichotomy. "Tentatively"
because if somebody can answer these objections than I will happily change
my mind
Here's an implementation of a turing machine simulator I hacked up a
while ago. For readability's sake, it's a function definition with a
doc-string, but the heart of it is a single list comprehension which
could be written without indentation:
def listcomp_turing(M, T, initial_state = 0):
"""Run the turing machine M on the tape T.
The tape T should be a dictionary mapping head positions to the
value on the tape at that position. Valid values on the tape are 0
and 1. Empty positions have the value 0. The initial head position
is 0.
The turing machine M should be a sequence of state pairs. The state
of the machine is used as an index into that sequence and thus
should be in range(len(M)). Each state pair is a pair of
(write_symbol, head_direction, next_state) triples, one for each of
the possible values on the tape at the current head position. The
initial state is given by the optional parameter initial_state. If
the next state is None, the machine stops. The direction may be
either -1 or 1 meaning left and right respectively. The function
does not enforce this limitation but with other values the machine
is not a turing machine anymore.
The return value is T.
"""
[x for L in [[[initial_state, 0]]]
for state, pos in L
if state is not None
and (L.append([M[state][T.get(pos, 0)][2],
pos + M[state][T.get(pos, 0)][1]])
or T.__setitem__(pos, M[state][T.get(pos, 0)][0]))]
return T
For an example, lets take the one from wikipedia's article on turing
machines:
The following Turing machine has an alphabet {'0', '1'}, with 0
being the blank symbol. It expects a series of 1's on the tape, with
the head initially on the leftmost 1, and doubles the 1's with a 0
in between, i.e., "111" becomes "1110111". The set of states is {s1,
s2, s3, s4, s5} and the start state is s1. The action table is as
follows.
Old Read Wr. New Old Read Wr. New
St. Sym. Sym. Mv. St. St. Sym. Sym. Mv. St.
- - - - - - - - - - - - - - - - - - - - - - - -
s1 1 -> 0 R s2 s4 1 -> 1 L s4
s2 1 -> 1 R s2 s4 0 -> 0 L s5
s2 0 -> 0 R s3 s5 1 -> 1 L s5
s3 0 -> 1 L s4 s5 0 -> 1 R s1
s3 1 -> 1 R s3
The listcomp_turing call with a tape containing "11" would be
listcomp_turing([((0, +1, None), (0, +1, 1)),
((0, +1, 2), (1, +1, 1)),
((1, -1, 3), (1, +1, 2)),
((0, -1, 4), (1, -1, 3)),
((1, +1, 0), (1, -1, 4))],
{0:1, 1:1})
which produces a result tape of
{0: 1, 1: 1, 2: 0, 3: 1, 4: 1}
Bernhard
