{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Turing Machine as a Python Generator" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This is a simulator of a Turing machine with a singly-infinite tape. You can run this notebook interactively using [IPython notebook](http://ipython.org/notebook.html). Refer to [this instructions](http://eecs.io/python-environment-for-scientific-computing.html) if you don't have Python or IPython installed." ] }, { "cell_type": "code", "execution_count": 34, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import logging\n", "\n", "from itertools import islice" ] }, { "cell_type": "code", "execution_count": 35, "metadata": { "collapsed": false }, "outputs": [], "source": [ "class TuringMachine:\n", " \"\"\"Turing machine with a singly-infinite tape.\n", "\n", " A machine is instantiated with transitions, start, accept and reject states\n", " and a blank symbol. We assume that the input and the tape alphabet can be\n", " deducted from the transitions.\n", "\n", " :param dict transitions: a mapping from (state, symbol) tuples to (state,\n", " symbol, direction) tuple. Note that in theory δ is a transition *function*\n", " (in the sense of mathematical functions), but we expect a mapping, not a\n", " callable. Directions are either 'L' (for left) or 'R' (for right).\n", "\n", " :param start_state: the initial state of the machine.\n", "\n", " :param accpet_state: the accept state.\n", "\n", " :param reject_state: the reject state.\n", "\n", " :blank_symbol: the special symbold that marks the tape cell to be empty.\n", "\n", " We don't really care what the input alphabet Σ and the tape alphabet Γ are\n", " for the purpose of this implementation. For a particular run of the machine,\n", " the tape alphabet is the union of the input, symbols used in transitions and\n", " the blank symbol.\n", "\n", " The input on the tape is not part of a Turing machine, so it's not required\n", " on a Turing machine instantiation. To execute a particular machine use the\n", " .run() instance method.\n", "\n", " \"\"\"\n", "\n", " def __init__(self, transitions, start_state='q0', accept_state='qa', reject_state='qr', blank_symbol=''):\n", " self.blank_symbol = blank_symbol\n", " self.transitions = transitions\n", " self.start_state = start_state\n", " self.reject_state = reject_state\n", "\n", " self.states_to_actions = {\n", " accept_state: 'Accept',\n", " reject_state: 'Reject',\n", " }\n", "\n", " def run(self, input_):\n", " \"\"\"Exectute the Turing machine for a particular input.\n", "\n", " :param input_: the input that is written on the tape. It's can be a list\n", " of strings. Or just a string, in which case each letter is treated as a\n", " symbol.\n", "\n", " Given an input a machine can run forever or stop after a number of\n", " steps. So it would be great if we could write a function that\n", " potentially runs forever and it's up the the caller to decide how many\n", " steps are executed. Actually, we should not even bother with this. On\n", " the other side, ^C is not the best way for a user to tell us to stop.\n", " Instead we give the user control to execute us one step at a time. This\n", " is what Python generators are (partially) for. The yield expression\n", " suspends us and gives controll to the caller until he or she decides to\n", " resume our execution. Have a look to [1] to get familliar with the yield\n", " keyord and generators, and hopefully never, ever write something like::\n", "\n", " result = []\n", " for i in range(len(other_items)):\n", " item = other_items[i]\n", "\n", " result.append(item * 3)\n", "\n", " At each step the generator yields a (action, configuration) tuple.\n", "\n", " The action is either 'Accept', 'Reject' or None. 'Accept' and `Reject`\n", " are self explanatory and signal that the input is either accepted or\n", " rejected the machine stops in these states. None is returned in case the\n", " machine needs to continue running.\n", "\n", " Configuration is a dictionary with the following keys:\n", " - 'state' the current state,\n", " - 'left_hand_side': the symbols on the left hand side of the\n", " current position.\n", " - 'symbol': the current symbol,\n", " - 'right_hand_side': the symbols on the right hand side of the\n", " current position.\n", "\n", " [1] http://www.jeffknupp.com/blog/2013/04/07/improve-your-python-yield-and-generators-explained/\n", "\n", " \"\"\"\n", " state = self.start_state\n", "\n", " # Theory doesn't say how to implement the tape, so we store the symbols\n", " # on the tape the way that is most suitable for us. We get two lists to\n", " # store the symbols from left and right hand sides of the current\n", " # symbol.\n", " #\n", " # Initially, there is the blank symbol on the left. Note, that the\n", " # element at 0 position is the *closest* to the head.\n", " left_hand_side = [self.blank_symbol]\n", " if not input_:\n", " # In case input is empty, pretend that it consists of a blank.\n", " input_ = [self.blank_symbol]\n", " # Consume the right most symbol of the input and make it the current\n", " # symbol, everything else is stored in a list for the right side\n", " # symbols.\n", " symbol = input_[0]\n", " right_hand_side = list(input_[1:])\n", "\n", " while True:\n", " # Share our state with the caller.\n", " # Also give them a chance to control our execution.\n", " action = self.states_to_actions.get(state)\n", " yield (\n", " action,\n", " {\n", " 'state': state,\n", " 'left_hand_side': left_hand_side,\n", " 'symbol': symbol,\n", " 'right_hand_side': right_hand_side,\n", " }\n", " )\n", "\n", " # Check whether we need to stop the execution.\n", " if action is not None:\n", " break\n", "\n", " # Do the transition.\n", " state, symbol, direction = self.transitions.get(\n", " (state, symbol),\n", " (self.reject_state, symbol, 'R'), # All other transitions are to the reject state.\n", " )\n", "\n", " if direction == 'R':\n", " left_hand_side.insert(0, symbol)\n", "\n", " try:\n", " symbol = right_hand_side.pop(0)\n", " except IndexError:\n", " # Pretend that we always have a blank symbol on the right.\n", " symbol = self.blank_symbol\n", "\n", " elif left_hand_side:\n", " # Move to the left only if there is a symbold to move.\n", " right_hand_side.insert(0, symbol)\n", " symbol = left_hand_side.pop(0)\n", "\n", " else:\n", " assert direction in 'LR', 'L (left) and R (right) are the only correct directions to move.'\n", " logging.warning('An attempt to move left from the leftmost cell! The machine stays put.')\n", "\n", " def accepts(self, input_, step_limit=100):\n", " action = list(islice(self.run(input_), step_limit))[-1][0]\n", "\n", " if action is not None:\n", " return action == 'Accept'\n", " else:\n", " logging.warn(\n", " 'The step limit of %s steps is reached!',\n", " step_limit,\n", " )\n", "\n", " def rejects(self, input_, **kwargs):\n", " accepts = self.accepts(input_, **kwargs)\n", "\n", " if accepts is not None:\n", " return not accepts\n", "\n", " def debug(self, input_, step_limit=100, colored=False):\n", " for action, configuration in islice(self.run(input_), step_limit):\n", " print(\n", " '{state:<30} {left}{b}{symbol}{f}{right}'.format(\n", " left=''.join(reversed(configuration['left_hand_side'])),\n", " right=''.join(configuration['right_hand_side']),\n", " b='\\x1b[47;1m' if colored else '[',\n", " f='\\x1b[0m' if colored else ']',\n", " **configuration\n", " )\n", " )\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# One hash" ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "collapsed": false }, "outputs": [], "source": [ "one_hash = TuringMachine(\n", " {\n", " ('q0', '#'): ('saw_#', '#', 'R'),\n", " ('saw_#', ''): ('qa', '', 'R'),\n", " }\n", ")" ] }, { "cell_type": "code", "execution_count": 37, "metadata": { "collapsed": false }, "outputs": [], "source": [ "execution = one_hash.run('#')" ] }, { "cell_type": "code", "execution_count": 38, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "(None,\n", " {'left_hand_side': [''], 'right_hand_side': [], 'state': 'q0', 'symbol': '#'})" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "next(execution)" ] }, { "cell_type": "code", "execution_count": 39, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "(None,\n", " {'left_hand_side': ['#', ''],\n", " 'right_hand_side': [],\n", " 'state': 'saw_#',\n", " 'symbol': ''})" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "next(execution)" ] }, { "cell_type": "code", "execution_count": 40, "metadata": { "collapsed": false, "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "('Accept',\n", " {'left_hand_side': ['', '#', ''],\n", " 'right_hand_side': [],\n", " 'state': 'qa',\n", " 'symbol': ''})" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "next(execution)" ] }, { "cell_type": "code", "execution_count": 41, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "one_hash.accepts('#')" ] }, { "cell_type": "code", "execution_count": 42, "metadata": { "collapsed": false }, "outputs": [], "source": [ "assert one_hash.accepts('#')" ] }, { "cell_type": "code", "execution_count": 43, "metadata": { "collapsed": false }, "outputs": [], "source": [ "assert one_hash.rejects('##')" ] }, { "cell_type": "code", "execution_count": 44, "metadata": { "collapsed": false }, "outputs": [], "source": [ "assert one_hash.rejects('')" ] }, { "cell_type": "code", "execution_count": 45, "metadata": { "collapsed": false }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "WARNING:root:The step limit of 1 steps is reached!\n" ] } ], "source": [ "assert one_hash.accepts('#', step_limit=1) is None" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Two hashes" ] }, { "cell_type": "code", "execution_count": 46, "metadata": { "collapsed": true }, "outputs": [], "source": [ "two_hashes = TuringMachine(\n", " {\n", " ('q0', '#'): ('saw_#', '#', 'R'),\n", " ('saw_#', '#'): ('saw_##', '#', 'R'),\n", " ('saw_##', ''): ('qa', '', 'R'),\n", " }\n", ")" ] }, { "cell_type": "code", "execution_count": 47, "metadata": { "collapsed": false }, "outputs": [], "source": [ "assert two_hashes.accepts('##')" ] }, { "cell_type": "code", "execution_count": 48, "metadata": { "collapsed": false }, "outputs": [], "source": [ "assert two_hashes.rejects('#')" ] }, { "cell_type": "code", "execution_count": 49, "metadata": { "collapsed": false }, "outputs": [], "source": [ "assert two_hashes.rejects('###')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Two same words separated by # (w#w)" ] }, { "cell_type": "code", "execution_count": 50, "metadata": { "collapsed": true }, "outputs": [], "source": [ "w_hash_w = TuringMachine(\n", " {\n", " ('q0', '#'): ('End', '#', 'R'),\n", " ('End', ''): ('qa', '', 'R'),\n", "\n", " ('q0', '0'): ('FindDelimiter0', 'X', 'R'),\n", " ('FindDelimiter0', '#'): ('Check0', '#', 'R'),\n", " ('Check0', '0'): ('FindLeftmost', 'X', 'L'),\n", "\n", " ('q0', '1'): ('FindDelimiter1', 'X', 'R'),\n", " ('FindDelimiter1', '#'): ('Check1', '#', 'R'),\n", " ('Check1', '1'): ('FindLeftmost', 'X', 'L'),\n", "\n", " ('FindLeftmost', '0'): ('FindLeftmost', '0', 'L'),\n", " ('FindLeftmost', '1'): ('FindLeftmost', '1', 'L'),\n", " ('FindLeftmost', 'X'): ('FindLeftmost', 'X', 'L'),\n", " ('FindLeftmost', '#'): ('FindLeftmost', '#', 'L'),\n", " ('FindLeftmost', ''): ('FindNext', '', 'R'),\n", " \n", " ('FindNext', 'X'): ('FindNext', 'X', 'R'),\n", " ('FindNext', '0'): ('FindDelimiter0', 'X', 'R'),\n", " ('FindNext', '1'): ('FindDelimiter1', 'X', 'R'),\n", " ('FindNext', '#'): ('End', '#', 'R'),\n", " \n", " ('FindDelimiter0', '0'): ('FindDelimiter0', '0', 'R'),\n", " ('FindDelimiter0', '1'): ('FindDelimiter0', '1', 'R'),\n", " ('FindDelimiter1', '0'): ('FindDelimiter1', '0', 'R'),\n", " ('FindDelimiter1', '1'): ('FindDelimiter1', '1', 'R'),\n", " \n", " ('Check0', 'X'): ('Check0', 'X', 'R'),\n", " ('Check1', 'X'): ('Check1', 'X', 'R'),\n", " \n", " ('End', 'X'): ('End', 'X', 'R')\n", " }\n", ")" ] }, { "cell_type": "code", "execution_count": 51, "metadata": { "collapsed": false }, "outputs": [], "source": [ "assert w_hash_w.accepts('#')" ] }, { "cell_type": "code", "execution_count": 52, "metadata": { "collapsed": false }, "outputs": [], "source": [ "assert w_hash_w.accepts('0#0')" ] }, { "cell_type": "code", "execution_count": 53, "metadata": { "collapsed": false }, "outputs": [], "source": [ "assert w_hash_w.accepts('1#1')" ] }, { "cell_type": "code", "execution_count": 54, "metadata": { "collapsed": false }, "outputs": [], "source": [ "assert w_hash_w.accepts('0000000000000#0000000000000', step_limit=10000)" ] }, { "cell_type": "code", "execution_count": 55, "metadata": { "collapsed": false }, "outputs": [], "source": [ "assert w_hash_w.accepts('1001#1001')" ] }, { "cell_type": "code", "execution_count": 56, "metadata": { "collapsed": true }, "outputs": [], "source": [ "assert w_hash_w.rejects('10#1')" ] }, { "cell_type": "code", "execution_count": 57, "metadata": { "collapsed": true }, "outputs": [], "source": [ "assert w_hash_w.rejects('1#01')" ] }, { "cell_type": "code", "execution_count": 58, "metadata": { "collapsed": true }, "outputs": [], "source": [ "assert w_hash_w.rejects('1#1#')" ] }, { "cell_type": "code", "execution_count": 59, "metadata": { "collapsed": true }, "outputs": [], "source": [ "assert w_hash_w.rejects('1##1')" ] }, { "cell_type": "code", "execution_count": 60, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "q0 \u001b[47;1m1\u001b[0m1#110\n", "FindDelimiter1 X\u001b[47;1m1\u001b[0m#110\n", "FindDelimiter1 X1\u001b[47;1m#\u001b[0m110\n", "Check1 X1#\u001b[47;1m1\u001b[0m10\n", "FindLeftmost X1\u001b[47;1m#\u001b[0mX10\n", "FindLeftmost X\u001b[47;1m1\u001b[0m#X10\n", "FindLeftmost \u001b[47;1mX\u001b[0m1#X10\n", "FindLeftmost \u001b[47;1m\u001b[0mX1#X10\n", "FindNext \u001b[47;1mX\u001b[0m1#X10\n", "FindNext X\u001b[47;1m1\u001b[0m#X10\n", "FindDelimiter1 XX\u001b[47;1m#\u001b[0mX10\n", "Check1 XX#\u001b[47;1mX\u001b[0m10\n", "Check1 XX#X\u001b[47;1m1\u001b[0m0\n", "FindLeftmost XX#\u001b[47;1mX\u001b[0mX0\n", "FindLeftmost XX\u001b[47;1m#\u001b[0mXX0\n", "FindLeftmost X\u001b[47;1mX\u001b[0m#XX0\n", "FindLeftmost \u001b[47;1mX\u001b[0mX#XX0\n", "FindLeftmost \u001b[47;1m\u001b[0mXX#XX0\n", "FindNext \u001b[47;1mX\u001b[0mX#XX0\n", "FindNext X\u001b[47;1mX\u001b[0m#XX0\n", "FindNext XX\u001b[47;1m#\u001b[0mXX0\n", "End XX#\u001b[47;1mX\u001b[0mX0\n", "End XX#X\u001b[47;1mX\u001b[0m0\n", "End XX#XX\u001b[47;1m0\u001b[0m\n", "qr XX#XX0\u001b[47;1m\u001b[0m\n" ] } ], "source": [ "w_hash_w.debug('11#110', colored=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Moving left" ] }, { "cell_type": "code", "execution_count": 61, "metadata": { "collapsed": false }, "outputs": [], "source": [ "move_left = TuringMachine(\n", " {\n", " ('q0', ''): ('q0', '', 'L'),\n", " }\n", ")" ] }, { "cell_type": "code", "execution_count": 62, "metadata": { "collapsed": false }, "outputs": [], "source": [ "execution = move_left.run('')" ] }, { "cell_type": "code", "execution_count": 63, "metadata": { "collapsed": false }, "outputs": [], "source": [ "assert next(execution) == (\n", " None,\n", " {\n", " 'left_hand_side': [''],\n", " 'right_hand_side': [],\n", " 'state': 'q0',\n", " 'symbol': '',\n", " },\n", ")" ] }, { "cell_type": "code", "execution_count": 64, "metadata": { "collapsed": false }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "WARNING:root:An attempt to move left from the leftmost cell! The machine stays put.\n", "WARNING:root:An attempt to move left from the leftmost cell! The machine stays put.\n" ] } ], "source": [ "for _ in range(3):\n", " assert next(execution) == (\n", " None,\n", " {\n", " 'left_hand_side': [],\n", " 'right_hand_side': [''],\n", " 'state': 'q0',\n", " 'symbol': '',\n", " },\n", ")" ] }, { "cell_type": "code", "execution_count": 65, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "\n", "
\n", " \n", " \n", " comments powered by Disqus\n", " " ], "text/plain": [ "" ] }, "execution_count": 65, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from IPython.display import HTML\n", "\n", "HTML(\n", " \"\"\"\n", "
\n", " \n", " \n", " comments powered by Disqus\n", " \"\"\"\n", ")\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.4.3" } }, "nbformat": 4, "nbformat_minor": 0 }