<commit_before>{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      ":0: FutureWarning: IPython widgets are experimental and may change in the future.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "\n",
       "<style type=\"text/css\">\n",
       "    .state {\n",
       "        width: 110px;\n",
       "        height: 50px;\n",
       "        background: pink;\n",
       "        font-weight: bold;\n",
       "    }\n",
       "    .box {\n",
       "        display: flex;\n",
       "        justify-content: center;\n",
       "        align-items: center;\n",
       "        border: 3px solid grey;\n",
       "        margin: 5px;\n",
       "        padding: 5px;\n",
       "    }\n",
       "    .tape {\n",
       "        width: 50px;\n",
       "        height: 50px;\n",
       "    }\n",
       "    .head {\n",
       "        background: yellow;\n",
       "        font-weight: bold;\n",
       "    }\n",
       "    .configuration {\n",
       "        display: flex;\n",
       "        flex-wrap: wrap;\n",
       "        flex-direction: row;\n",
       "    }\n",
       "</style>\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%run -i turing.py\n",
    "init()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Turing machine computation\n",
    "\n",
    "## Tape\n",
    "\n",
    "We will represent the tape as a list of *tape symbols* and we will represent tape symbols as Python strings.\n",
    "The string `' '` represents the *blank symbol*.\n",
    "The string `'|>'` represents the *start symbol*, which indicates the beginning of the tape.\n",
    "\n",
    "## States\n",
    "\n",
    "We will also encode states as Python strings. \n",
    "The string `'start'` represents that start state.\n",
    "The strings `'accept'`, `'reject'`, and `'halt'` represent final states of the machine, that indicate acceptance, rejection, and halting, respectively. \n",
    "\n",
    "## Simulation\n",
    "\n",
    "The following function simulates a given Turing machine for a given number of steps on a given input"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def run(transitions, input, steps):\n",
    "    \"\"\"simulate Turing machine for the given number of steps and the given input\"\"\"\n",
    "\n",
    "    # convert input from string to list of symbols\n",
    "    # we use '|>' as a symbol to indicate the beginning of the tape\n",
    "    input = ['|>'] + list(input) + [' ']\n",
    "\n",
    "    # sanitize transitions for 'accept' and 'reject' states and for symbol '|>'\n",
    "    transitions = sanitize_transitions(transitions)\n",
    "\n",
    "    # create initial configuration\n",
    "    c = Configuration(state='start', head=1, tape=input)\n",
    "\n",
    "    for i in xrange(0, steps):\n",
    "        # read tape content under head\n",
    "        current = c.state\n",
    "        read = c.tape[c.head]\n",
    "\n",
    "        # lookup transition based on state and read symbol\n",
    "        next, write, move = transitions(current, read)\n",
    "\n",
    "        # update configuration\n",
    "        c.state = next\n",
    "        c.tape[c.head] = write\n",
    "        c.head += move\n",
    "        if c.head >= len(c.tape):\n",
    "            c.tape += [' ']\n",
    "\n",
    "    # return final configuration\n",
    "    return c\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following function checks that the transition functions satisfies some simple syntactic requirements (don't move to the left of the start symbol, don't remove or add start symbols, don't change state after accepting, rejecting, or halting.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def check_transitions(transitions, states, alphabet):\n",
    "\n",
    "    transitions = sanitize_transitions(transitions)\n",
    "\n",
    "    for current in states:\n",
    "        for read in alphabet:\n",
    "            next, write, move = transitions(current, read)\n",
    "\n",
    "            # we either move one position to the left or to the right\n",
    "            assert(move in [-1,1])\n",
    "\n",
    "            # if we read the begin symbol,\n",
    "            if read == '|>':\n",
    "                # we need to write it back\n",
    "                assert(write == '|>')\n",<commit_msg>allow head to stay in place in check transitions<commit_after>{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      ":0: FutureWarning: IPython widgets are experimental and may change in the future.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "\n",
       "<style type=\"text/css\">\n",
       "    .state {\n",
       "        width: 110px;\n",
       "        height: 50px;\n",
       "        background: pink;\n",
       "        font-weight: bold;\n",
       "    }\n",
       "    .box {\n",
       "        display: flex;\n",
       "        justify-content: center;\n",
       "        align-items: center;\n",
       "        border: 3px solid grey;\n",
       "        margin: 5px;\n",
       "        padding: 5px;\n",
       "    }\n",
       "    .tape {\n",
       "        width: 50px;\n",
       "        height: 50px;\n",
       "    }\n",
       "    .head {\n",
       "        background: yellow;\n",
       "        font-weight: bold;\n",
       "    }\n",
       "    .configuration {\n",
       "        display: flex;\n",
       "        flex-wrap: wrap;\n",
       "        flex-direction: row;\n",
       "    }\n",
       "</style>\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%run -i turing.py\n",
    "init()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Turing machine computation\n",
    "\n",
    "## Tape\n",
    "\n",
    "We will represent the tape as a list of *tape symbols* and we will represent tape symbols as Python strings.\n",
    "The string `' '` represents the *blank symbol*.\n",
    "The string `'|>'` represents the *start symbol*, which indicates the beginning of the tape.\n",
    "\n",
    "## States\n",
    "\n",
    "We will also encode states as Python strings. \n",
    "The string `'start'` represents that start state.\n",
    "The strings `'accept'`, `'reject'`, and `'halt'` represent final states of the machine, that indicate acceptance, rejection, and halting, respectively. \n",
    "\n",
    "## Simulation\n",
    "\n",
    "The following function simulates a given Turing machine for a given number of steps on a given input"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def run(transitions, input, steps):\n",
    "    \"\"\"simulate Turing machine for the given number of steps and the given input\"\"\"\n",
    "\n",
    "    # convert input from string to list of symbols\n",
    "    # we use '|>' as a symbol to indicate the beginning of the tape\n",
    "    input = ['|>'] + list(input) + [' ']\n",
    "\n",
    "    # sanitize transitions for 'accept' and 'reject' states and for symbol '|>'\n",
    "    transitions = sanitize_transitions(transitions)\n",
    "\n",
    "    # create initial configuration\n",
    "    c = Configuration(state='start', head=1, tape=input)\n",
    "\n",
    "    for i in xrange(0, steps):\n",
    "        # read tape content under head\n",
    "        current = c.state\n",
    "        read = c.tape[c.head]\n",
    "\n",
    "        # lookup transition based on state and read symbol\n",
    "        next, write, move = transitions(current, read)\n",
    "\n",
    "        # update configuration\n",
    "        c.state = next\n",
    "        c.tape[c.head] = write\n",
    "        c.head += move\n",
    "        if c.head >= len(c.tape):\n",
    "            c.tape += [' ']\n",
    "\n",
    "    # return final configuration\n",
    "    return c\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following function checks that the transition functions satisfies some simple syntactic requirements (don't move to the left of the start symbol, don't remove or add start symbols, don't change state after accepting, rejecting, or halting.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def check_transitions(transitions, states, alphabet):\n",
    "\n",
    "    transitions = sanitize_transitions(transitions)\n",
    "\n",
    "    for current in states:\n",
    "        for read in alphabet:\n",
    "            next, write, move = transitions(current, read)\n",
    "\n",
    "            # we either stay in place or move one position\n",
    "            # to the left or right\n",
    "            assert(move in [-1,0,1])\n",
    "\n",
    "            # if we read the begin symbol,\n",
    "            if read == '|>':\n",
    "                # we need to write it back\n",
    "                assert(write == '|>')\n",
{'fraction_non_alphanumeric': 0.17582644628099173, 'fraction_numerical': 0.004235537190082644, 'mean_word_length': 1.7842968075927523, 'pattern_counts': {'":': 66, '<': 7, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3264265', 'n_tokens_mistral': 3177, 'n_tokens_neox': 3120, 'n_words': 861}