turing machine in an LC

[Bernhard Herzog]

Jeremy Bowers <jerf at jerf.org> writes:

> On Tue, 08 Feb 2005 17:36:19 +0100, Bernhard Herzog wrote:
>> Nick Vargish <nav+posts at bandersnatch.org> writes:
>>> "Xah Lee" <xah at xahlee.org> writes:
>>>> is it possible to write python code without any indentation?
>>> Not if Turing-completeness is something you desire.
>> 
>> It's possible to implement a turing machine with a single list
>> comprehension.  No indentation needed.
>
> 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

-- 
Intevation GmbH                                 http://intevation.de/
Skencil                                           http://skencil.org/
Thuban                                  http://thuban.intevation.org/