Turing Machine as a Python Generator

This is a simulator of a Turing machine with a singly-infinite tape. You can run this notebook interactively using IPython notebook. Refer to this instructions if you don't have Python or IPython installed.

In [34]:
import logging

from itertools import islice
In [35]:
class TuringMachine:
    """Turing machine with a singly-infinite tape.

    A machine is instantiated with transitions, start, accept and reject states
    and a blank symbol. We assume that the input and the tape alphabet can be
    deducted from the transitions.

    :param dict transitions: a mapping from (state, symbol) tuples to (state,
    symbol, direction) tuple. Note that in theory δ is a transition *function*
    (in the sense of mathematical functions), but we expect a mapping, not a
    callable. Directions are either 'L' (for left) or 'R' (for right).

    :param start_state: the initial state of the machine.

    :param accpet_state: the accept state.

    :param reject_state: the reject state.

    :blank_symbol: the special symbold that marks the tape cell to be empty.

    We don't really care what the input alphabet Σ and the tape alphabet Γ are
    for the purpose of this implementation. For a particular run of the machine,
    the tape alphabet is the union of the input, symbols used in transitions and
    the blank symbol.

    The input on the tape is not part of a Turing machine, so it's not required
    on a Turing  machine instantiation. To execute a particular machine use the
    .run() instance method.

    """

    def __init__(self, transitions, start_state='q0', accept_state='qa', reject_state='qr', blank_symbol=''):
        self.blank_symbol = blank_symbol
        self.transitions = transitions
        self.start_state = start_state
        self.reject_state = reject_state

        self.states_to_actions = {
            accept_state: 'Accept',
            reject_state: 'Reject',
        }

    def run(self, input_):
        """Exectute the Turing machine for a particular input.

        :param input_: the input that is written on the tape. It's can be a list
        of strings. Or just a string, in which case each letter is treated as a
        symbol.

        Given an input a machine can run forever or stop after a number of
        steps. So it would be great if we could write a function that
        potentially runs forever and it's up the the caller to decide how many
        steps are executed. Actually, we should not even bother with this. On
        the other side, ^C is not the best way for a user to tell us to stop.
        Instead we give the user control to execute us one step at a time. This
        is what Python generators are (partially) for. The yield expression
        suspends us and gives controll to the caller until he or she decides to
        resume our execution. Have a look to [1] to get familliar with the yield
        keyord and generators, and hopefully never, ever write something like::

            result = []
            for i in range(len(other_items)):
                item = other_items[i]

                result.append(item * 3)

        At each step the generator yields a (action, configuration) tuple.

        The action is either 'Accept', 'Reject' or None. 'Accept' and `Reject`
        are self explanatory and signal that the input is either accepted or
        rejected the machine stops in these states. None is returned in case the
        machine needs to continue running.

        Configuration is a dictionary with the following keys:
        - 'state' the current state,
        - 'left_hand_side': the symbols on the left hand side of the
          current position.
        - 'symbol': the current symbol,
        - 'right_hand_side': the symbols on the right hand side of the
          current position.

        [1] http://www.jeffknupp.com/blog/2013/04/07/improve-your-python-yield-and-generators-explained/

        """
        state = self.start_state

        # Theory doesn't say how to implement the tape, so we store the symbols
        # on the tape the way that is most suitable for us. We get two lists to
        # store the symbols from left and right hand sides of the current
        # symbol.
        #
        # Initially, there is the blank symbol on the left. Note, that the
        # element at 0 position is the *closest* to the head.
        left_hand_side = [self.blank_symbol]
        if not input_:
            # In case input is empty, pretend that it consists of a blank.
            input_ = [self.blank_symbol]
        # Consume the right most symbol of the input and make it the current
        # symbol, everything else is stored in a list for the right side
        # symbols.
        symbol = input_[0]
        right_hand_side = list(input_[1:])

        while True:
            # Share our state with the caller.
            # Also give them a chance to control our execution.
            action = self.states_to_actions.get(state)
            yield (
                action,
                {
                    'state': state,
                    'left_hand_side': left_hand_side,
                    'symbol': symbol,
                    'right_hand_side': right_hand_side,
                }
            )

            # Check whether we need to stop the execution.
            if action is not None:
                break

            # Do the transition.
            state, symbol, direction = self.transitions.get(
                (state, symbol),
                (self.reject_state, symbol, 'R'),  # All other transitions are to the reject state.
            )

            if direction == 'R':
                left_hand_side.insert(0, symbol)

                try:
                    symbol = right_hand_side.pop(0)
                except IndexError:
                    # Pretend that we always have a blank symbol on the right.
                    symbol = self.blank_symbol

            elif left_hand_side:
                # Move to the left only if there is a symbold to move.
                right_hand_side.insert(0, symbol)
                symbol = left_hand_side.pop(0)

            else:
                assert direction in 'LR', 'L (left) and R (right) are the only correct directions to move.'
                logging.warning('An attempt to move left from the leftmost cell! The machine stays put.')

    def accepts(self, input_, step_limit=100):
        action = list(islice(self.run(input_), step_limit))[-1][0]

        if action is not None:
            return action == 'Accept'
        else:
            logging.warn(
                'The step limit of %s steps  is reached!',
                step_limit,
            )

    def rejects(self, input_, **kwargs):
        accepts = self.accepts(input_, **kwargs)

        if accepts is not None:
            return not accepts

    def debug(self, input_, step_limit=100, colored=False):
        for action, configuration in islice(self.run(input_), step_limit):
            print(
                '{state:<30} {left}{b}{symbol}{f}{right}'.format(
                    left=''.join(reversed(configuration['left_hand_side'])),
                    right=''.join(configuration['right_hand_side']),
                    b='\x1b[47;1m' if colored else '[',
                    f='\x1b[0m' if colored else ']',
                    **configuration
                )
            )

One hash

In [36]:
one_hash = TuringMachine(
    {
        ('q0', '#'): ('saw_#', '#', 'R'),
        ('saw_#', ''): ('qa', '', 'R'),
    }
)
In [37]:
execution = one_hash.run('#')
In [38]:
next(execution)
Out[38]:
(None,
 {'left_hand_side': [''], 'right_hand_side': [], 'state': 'q0', 'symbol': '#'})
In [39]:
next(execution)
Out[39]:
(None,
 {'left_hand_side': ['#', ''],
  'right_hand_side': [],
  'state': 'saw_#',
  'symbol': ''})
In [40]:
next(execution)
Out[40]:
('Accept',
 {'left_hand_side': ['', '#', ''],
  'right_hand_side': [],
  'state': 'qa',
  'symbol': ''})
In [41]:
one_hash.accepts('#')
Out[41]:
True
In [42]:
assert one_hash.accepts('#')
In [43]:
assert one_hash.rejects('##')
In [44]:
assert one_hash.rejects('')
In [45]:
assert one_hash.accepts('#', step_limit=1) is None
WARNING:root:The step limit of 1 steps  is reached!

Two hashes

In [46]:
two_hashes = TuringMachine(
    {
        ('q0', '#'): ('saw_#', '#', 'R'),
        ('saw_#', '#'): ('saw_##', '#', 'R'),
        ('saw_##', ''): ('qa', '', 'R'),
    }
)
In [47]:
assert two_hashes.accepts('##')
In [48]:
assert two_hashes.rejects('#')
In [49]:
assert two_hashes.rejects('###')

Two same words separated by # (w#w)

In [50]:
w_hash_w = TuringMachine(
    {
        ('q0', '#'): ('End', '#', 'R'),
        ('End', ''): ('qa', '', 'R'),

        ('q0', '0'): ('FindDelimiter0', 'X', 'R'),
        ('FindDelimiter0', '#'): ('Check0', '#', 'R'),
        ('Check0', '0'): ('FindLeftmost', 'X', 'L'),

        ('q0', '1'): ('FindDelimiter1', 'X', 'R'),
        ('FindDelimiter1', '#'): ('Check1', '#', 'R'),
        ('Check1', '1'): ('FindLeftmost', 'X', 'L'),

        ('FindLeftmost', '0'): ('FindLeftmost', '0', 'L'),
        ('FindLeftmost', '1'): ('FindLeftmost', '1', 'L'),
        ('FindLeftmost', 'X'): ('FindLeftmost', 'X', 'L'),
        ('FindLeftmost', '#'): ('FindLeftmost', '#', 'L'),
        ('FindLeftmost', ''): ('FindNext', '', 'R'),
        
        ('FindNext', 'X'): ('FindNext', 'X', 'R'),
        ('FindNext', '0'): ('FindDelimiter0', 'X', 'R'),
        ('FindNext', '1'): ('FindDelimiter1', 'X', 'R'),
        ('FindNext', '#'): ('End', '#', 'R'),
        
        ('FindDelimiter0', '0'): ('FindDelimiter0', '0', 'R'),
        ('FindDelimiter0', '1'): ('FindDelimiter0', '1', 'R'),
        ('FindDelimiter1', '0'): ('FindDelimiter1', '0', 'R'),
        ('FindDelimiter1', '1'): ('FindDelimiter1', '1', 'R'),
        
        ('Check0', 'X'): ('Check0', 'X', 'R'),
        ('Check1', 'X'): ('Check1', 'X', 'R'),
        
        ('End', 'X'): ('End', 'X', 'R')
    }
)
In [51]:
assert w_hash_w.accepts('#')
In [52]:
assert w_hash_w.accepts('0#0')
In [53]:
assert w_hash_w.accepts('1#1')
In [54]:
assert w_hash_w.accepts('0000000000000#0000000000000', step_limit=10000)
In [55]:
assert w_hash_w.accepts('1001#1001')
In [56]:
assert w_hash_w.rejects('10#1')
In [57]:
assert w_hash_w.rejects('1#01')
In [58]:
assert w_hash_w.rejects('1#1#')
In [59]:
assert w_hash_w.rejects('1##1')
In [60]:
w_hash_w.debug('11#110', colored=True)
q0                             11#110
FindDelimiter1                 X1#110
FindDelimiter1                 X1#110
Check1                         X1#110
FindLeftmost                   X1#X10
FindLeftmost                   X1#X10
FindLeftmost                   X1#X10
FindLeftmost                   X1#X10
FindNext                       X1#X10
FindNext                       X1#X10
FindDelimiter1                 XX#X10
Check1                         XX#X10
Check1                         XX#X10
FindLeftmost                   XX#XX0
FindLeftmost                   XX#XX0
FindLeftmost                   XX#XX0
FindLeftmost                   XX#XX0
FindLeftmost                   XX#XX0
FindNext                       XX#XX0
FindNext                       XX#XX0
FindNext                       XX#XX0
End                            XX#XX0
End                            XX#XX0
End                            XX#XX0
qr                             XX#XX0

Moving left

In [61]:
move_left = TuringMachine(
    {
        ('q0', ''): ('q0', '', 'L'),
    }
)
In [62]:
execution = move_left.run('')
In [63]:
assert next(execution) == (
    None,
    {
        'left_hand_side': [''],
        'right_hand_side': [],
        'state': 'q0',
        'symbol': '',
    },
)
In [64]:
for _ in range(3):
    assert next(execution) == (
        None,
        {
            'left_hand_side': [],
            'right_hand_side': [''],
            'state': 'q0',
            'symbol': '',
        },
)
WARNING:root:An attempt to move left from the leftmost cell! The machine stays put.
WARNING:root:An attempt to move left from the leftmost cell! The machine stays put.
In [65]:
from IPython.display import HTML

HTML(
    """
    <div id="disqus_thread"></div>
    <script type="text/javascript">
        /* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */
        var disqus_shortname = 'notebookcomments'; // required: replace example with your forum shortname

        /* * * DON'T EDIT BELOW THIS LINE * * */
        (function() {
            var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
            dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
            (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
        })();
    </script>
    <noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
    <a href="http://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>
    """
)
Out[65]:
comments powered by Disqus
In [ ]: