Chap_07_TM.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Chapters 7-9 : Turing Machines and Universal TM\n",
    "\n",
    "Code related to [Chapter 7: Loops and Infinity](https://introtcs.org/public/lec_06_loops.html) and [Chapter 9: Universality and Uncomputablity](https://introtcs.org/public/lec_08_uncomputability.html)  in __Introduction to Theoretical Computer Science__ by Boaz Barak. [![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/boazbk/tcscode/blob/master/Chap_07_TM.ipynb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!wget https://raw.githubusercontent.com/boazbk/tcscode/master/Utilities.ipynb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!pip install schemdraw"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# utility code \n",
    "%run \"Utilities.ipynb\"\n",
    "from IPython.display import clear_output\n",
    "clear_output()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def myred(x):\n",
    "    CRED = '\\033[91m'\n",
    "    CEND = '\\033[0m'\n",
    "    return CRED+x+CEND\n",
    "\n",
    "def mygreen(x):\n",
    "    CGREEN= '\\033[32m'\n",
    "    CEND = '\\033[0m'\n",
    "    return CGREEN+x+CEND\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": []
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       "  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Created with matplotlib (https://matplotlib.org/) -->\r\n",
       "<svg height=\"167.13072pt\" version=\"1.1\" viewBox=\"0 0 353.5708 167.13072\" width=\"353.5708pt\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       " <defs>\r\n",
       "  <style type=\"text/css\">\r\n",
       "*{stroke-linecap:butt;stroke-linejoin:round;}\r\n",
       "  </style>\r\n",
       " </defs>\r\n",
       " <g id=\"figure_1\">\r\n",
       "  <g id=\"patch_1\">\r\n",
       "   <path d=\"M 0 167.13072 \r\n",
       "L 353.5708 167.13072 \r\n",
       "L 353.5708 0 \r\n",
       "L 0 0 \r\n",
       "z\r\n",
       "\" style=\"fill:none;\"/>\r\n",
       "  </g>\r\n",
       "  <g id=\"axes_1\">\r\n",
       "   <g id=\"patch_2\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 26.8668 30.44376 \r\n",
       "C 27.382355 30.44376 27.876863 30.250307 28.241416 29.906008 \r\n",
       "C 28.605968 29.561709 28.8108 29.094673 28.8108 28.60776 \r\n",
       "C 28.8108 28.120847 28.605968 27.653811 28.241416 27.309512 \r\n",
       "C 27.876863 26.965213 27.382355 26.77176 26.8668 26.77176 \r\n",
       "C 26.351245 26.77176 25.856737 26.965213 25.492184 27.309512 \r\n",
       "C 25.127632 27.653811 24.9228 28.120847 24.9228 28.60776 \r\n",
       "C 24.9228 29.094673 25.127632 29.561709 25.492184 29.906008 \r\n",
       "C 25.856737 30.250307 26.351245 30.44376 26.8668 30.44376 \r\n",
       "z\r\n",
       "\" style=\"stroke:#000000;stroke-linejoin:miter;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"patch_3\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 26.8668 140.60376 \r\n",
       "C 27.382355 140.60376 27.876863 140.410307 28.241416 140.066008 \r\n",
       "C 28.605968 139.721709 28.8108 139.254673 28.8108 138.76776 \r\n",
       "C 28.8108 138.280847 28.605968 137.813811 28.241416 137.469512 \r\n",
       "C 27.876863 137.125213 27.382355 136.93176 26.8668 136.93176 \r\n",
       "C 26.351245 136.93176 25.856737 137.125213 25.492184 137.469512 \r\n",
       "C 25.127632 137.813811 24.9228 138.280847 24.9228 138.76776 \r\n",
       "C 24.9228 139.254673 25.127632 139.721709 25.492184 140.066008 \r\n",
       "C 25.856737 140.410307 26.351245 140.60376 26.8668 140.60376 \r\n",
       "z\r\n",
       "\" style=\"stroke:#000000;stroke-linejoin:miter;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"patch_4\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 201.8268 35.624952 \r\n",
       "C 202.651688 35.624952 203.442901 35.315428 204.026185 34.764549 \r\n",
       "C 204.609469 34.21367 204.9372 33.466413 204.9372 32.687352 \r\n",
       "C 204.9372 31.908291 204.609469 31.161034 204.026185 30.610155 \r\n",
       "C 203.442901 30.059276 202.651688 29.749752 201.8268 29.749752 \r\n",
       "C 201.001912 29.749752 200.210699 30.059276 199.627415 30.610155 \r\n",
       "C 199.044131 31.161034 198.7164 31.908291 198.7164 32.687352 \r\n",
       "C 198.7164 33.466413 199.044131 34.21367 199.627415 34.764549 \r\n",
       "C 200.210699 35.315428 201.001912 35.624952 201.8268 35.624952 \r\n",
       "z\r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linejoin:miter;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_1\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 26.8668 28.60776 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_2\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 26.8668 138.76776 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_3\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 130.5468 40.84776 \r\n",
       "L 131.37715 40.822612 \r\n",
       "L 132.204088 40.74727 \r\n",
       "L 133.024216 40.622044 \r\n",
       "L 133.834163 40.447449 \r\n",
       "L 134.630603 40.224202 \r\n",
       "L 135.41026 39.953221 \r\n",
       "L 136.169933 39.635619 \r\n",
       "L 136.906499 39.272701 \r\n",
       "L 137.616932 38.865958 \r\n",
       "L 138.298312 38.417063 \r\n",
       "L 138.94784 37.927859 \r\n",
       "L 139.562846 37.400356 \r\n",
       "L 140.140803 36.836723 \r\n",
       "L 140.679336 36.239275 \r\n",
       "L 141.176232 35.610468 \r\n",
       "L 141.62945 34.952885 \r\n",
       "L 142.037127 34.269229 \r\n",
       "L 142.397588 33.562308 \r\n",
       "L 142.709351 32.835028 \r\n",
       "L 142.971135 32.090378 \r\n",
       "L 143.181866 31.331416 \r\n",
       "L 143.340676 30.561263 \r\n",
       "L 143.446913 29.783082 \r\n",
       "L 143.500141 29.000071 \r\n",
       "L 143.500141 28.215449 \r\n",
       "L 143.446913 27.432438 \r\n",
       "L 143.340676 26.654257 \r\n",
       "L 143.181866 25.884104 \r\n",
       "L 142.971135 25.125142 \r\n",
       "L 142.709351 24.380492 \r\n",
       "L 142.397588 23.653212 \r\n",
       "L 142.037127 22.946291 \r\n",
       "L 141.62945 22.262635 \r\n",
       "L 141.176232 21.605052 \r\n",
       "L 140.679336 20.976245 \r\n",
       "L 140.140803 20.378797 \r\n",
       "L 139.562846 19.815164 \r\n",
       "L 138.94784 19.287661 \r\n",
       "L 138.298312 18.798457 \r\n",
       "L 137.616932 18.349562 \r\n",
       "L 136.906499 17.942819 \r\n",
       "L 136.169933 17.579901 \r\n",
       "L 135.41026 17.262299 \r\n",
       "L 134.630603 16.991318 \r\n",
       "L 133.834163 16.768071 \r\n",
       "L 133.024216 16.593476 \r\n",
       "L 132.204088 16.46825 \r\n",
       "L 131.37715 16.392908 \r\n",
       "L 130.5468 16.36776 \r\n",
       "L 113.6988 16.36776 \r\n",
       "L 113.6988 28.60776 \r\n",
       "L 113.6988 40.84776 \r\n",
       "L 130.5468 40.84776 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_4\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 104.6268 34.72776 \r\n",
       "L 113.6988 34.72776 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_5\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 104.6268 22.48776 \r\n",
       "L 113.6988 22.48776 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_6\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 104.6268 28.60776 \r\n",
       "M 143.5068 28.60776 \r\n",
       "L 152.5788 28.60776 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_7\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 26.8668 28.60776 \r\n",
       "L 65.7468 25.54776 \r\n",
       "L 104.6268 22.48776 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_8\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 26.8668 138.76776 \r\n",
       "L 65.7468 86.74776 \r\n",
       "L 104.6268 34.72776 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_9\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 181.8684 32.687352 \r\n",
       "L 181.8684 44.927352 \r\n",
       "L 198.7164 32.687352 \r\n",
       "L 181.8684 20.447352 \r\n",
       "L 181.8684 32.687352 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_10\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 204.9372 32.687352 \r\n",
       "L 207.7884 32.687352 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_11\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 182.3868 32.687352 \r\n",
       "L 172.7964 32.687352 \r\n",
       "L 181.8684 32.687352 \r\n",
       "M 204.9372 32.687352 \r\n",
       "L 195.3468 32.687352 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_12\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 152.5788 28.60776 \r\n",
       "L 167.4828 30.647556 \r\n",
       "L 182.3868 32.687352 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_13\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 113.6988 150.76296 \r\n",
       "L 128.139943 150.683025 \r\n",
       "L 129.991371 150.358291 \r\n",
       "L 131.8428 149.78376 \r\n",
       "L 133.694229 148.959433 \r\n",
       "L 135.545657 147.885311 \r\n",
       "L 137.397086 146.561393 \r\n",
       "L 139.248514 144.987678 \r\n",
       "L 141.470229 142.769491 \r\n",
       "L 143.691943 140.191597 \r\n",
       "L 144.8028 138.76776 \r\n",
       "L 144.8028 138.76776 \r\n",
       "L 142.581086 136.010013 \r\n",
       "L 140.359371 133.611972 \r\n",
       "L 138.137657 131.573638 \r\n",
       "L 136.286229 130.149801 \r\n",
       "L 134.4348 128.97576 \r\n",
       "L 132.583371 128.051515 \r\n",
       "L 130.731943 127.377066 \r\n",
       "L 128.880514 126.952413 \r\n",
       "L 127.029086 126.777556 \r\n",
       "L 126.6588 126.77256 \r\n",
       "L 113.6988 126.77256 \r\n",
       "L 113.6988 126.77256 \r\n",
       "L 115.56504 128.73096 \r\n",
       "L 117.099504 130.68936 \r\n",
       "L 118.302192 132.64776 \r\n",
       "L 119.173104 134.60616 \r\n",
       "L 119.60856 136.07496 \r\n",
       "L 119.857392 137.54376 \r\n",
       "L 119.9196 139.01256 \r\n",
       "L 119.795184 140.48136 \r\n",
       "L 119.484144 141.95016 \r\n",
       "L 118.98648 143.41896 \r\n",
       "L 118.302192 144.88776 \r\n",
       "L 117.099504 146.84616 \r\n",
       "L 115.56504 148.80456 \r\n",
       "L 113.6988 150.76296 \r\n",
       "L 113.6988 150.76296 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_14\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 104.6268 144.88776 \r\n",
       "L 118.302192 144.88776 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_15\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 104.6268 132.64776 \r\n",
       "L 118.302192 132.64776 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_16\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 104.6268 138.76776 \r\n",
       "M 144.8028 138.76776 \r\n",
       "L 153.8748 138.76776 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_17\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 26.8668 28.60776 \r\n",
       "L 65.7468 80.62776 \r\n",
       "L 104.6268 132.64776 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_18\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 26.8668 138.76776 \r\n",
       "L 65.7468 141.82776 \r\n",
       "L 104.6268 144.88776 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_19\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 305.5068 93.886128 \r\n",
       "L 306.33715 93.86098 \r\n",
       "L 307.164088 93.785638 \r\n",
       "L 307.984216 93.660412 \r\n",
       "L 308.794163 93.485817 \r\n",
       "L 309.590603 93.26257 \r\n",
       "L 310.37026 92.991589 \r\n",
       "L 311.129933 92.673987 \r\n",
       "L 311.866499 92.311069 \r\n",
       "L 312.576932 91.904326 \r\n",
       "L 313.258312 91.455431 \r\n",
       "L 313.90784 90.966227 \r\n",
       "L 314.522846 90.438724 \r\n",
       "L 315.100803 89.875091 \r\n",
       "L 315.639336 89.277643 \r\n",
       "L 316.136232 88.648836 \r\n",
       "L 316.58945 87.991253 \r\n",
       "L 316.997127 87.307597 \r\n",
       "L 317.357588 86.600676 \r\n",
       "L 317.669351 85.873396 \r\n",
       "L 317.931135 85.128746 \r\n",
       "L 318.141866 84.369784 \r\n",
       "L 318.300676 83.599631 \r\n",
       "L 318.406913 82.82145 \r\n",
       "L 318.460141 82.038439 \r\n",
       "L 318.460141 81.253817 \r\n",
       "L 318.406913 80.470806 \r\n",
       "L 318.300676 79.692625 \r\n",
       "L 318.141866 78.922472 \r\n",
       "L 317.931135 78.16351 \r\n",
       "L 317.669351 77.41886 \r\n",
       "L 317.357588 76.69158 \r\n",
       "L 316.997127 75.984659 \r\n",
       "L 316.58945 75.301003 \r\n",
       "L 316.136232 74.64342 \r\n",
       "L 315.639336 74.014613 \r\n",
       "L 315.100803 73.417165 \r\n",
       "L 314.522846 72.853532 \r\n",
       "L 313.90784 72.326029 \r\n",
       "L 313.258312 71.836825 \r\n",
       "L 312.576932 71.38793 \r\n",
       "L 311.866499 70.981187 \r\n",
       "L 311.129933 70.618269 \r\n",
       "L 310.37026 70.300667 \r\n",
       "L 309.590603 70.029686 \r\n",
       "L 308.794163 69.806439 \r\n",
       "L 307.984216 69.631844 \r\n",
       "L 307.164088 69.506618 \r\n",
       "L 306.33715 69.431276 \r\n",
       "L 305.5068 69.406128 \r\n",
       "L 288.6588 69.406128 \r\n",
       "L 288.6588 81.646128 \r\n",
       "L 288.6588 93.886128 \r\n",
       "L 305.5068 93.886128 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_20\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 279.5868 87.766128 \r\n",
       "L 288.6588 87.766128 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_21\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 279.5868 75.526128 \r\n",
       "L 288.6588 75.526128 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_22\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 279.5868 81.646128 \r\n",
       "M 318.4668 81.646128 \r\n",
       "L 327.5388 81.646128 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_23\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 208.3068 32.687352 \r\n",
       "L 243.9468 54.10674 \r\n",
       "L 279.5868 75.526128 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_24\">\r\n",
       "    <path clip-path=\"url(#p6292f6e2f4)\" d=\"M 153.8748 138.76776 \r\n",
       "L 216.7308 113.266944 \r\n",
       "L 279.5868 87.766128 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:2;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"text_1\">\r\n",
       "    <!-- $X[0]$ -->\r\n",
       "    <defs>\r\n",
       "     <path d=\"M 6.296875 72.90625 \r\n",
       "L 16.890625 72.90625 \r\n",
       "L 35.015625 45.796875 \r\n",
       "L 53.21875 72.90625 \r\n",
       "L 63.8125 72.90625 \r\n",
       "L 40.375 37.890625 \r\n",
       "L 65.375 0 \r\n",
       "L 54.78125 0 \r\n",
       "L 34.28125 31 \r\n",
       "L 13.625 0 \r\n",
       "L 2.984375 0 \r\n",
       "L 29 38.921875 \r\n",
       "z\r\n",
       "\" id=\"DejaVuSans-88\"/>\r\n",
       "     <path d=\"M 8.59375 75.984375 \r\n",
       "L 29.296875 75.984375 \r\n",
       "L 29.296875 69 \r\n",
       "L 17.578125 69 \r\n",
       "L 17.578125 -6.203125 \r\n",
       "L 29.296875 -6.203125 \r\n",
       "L 29.296875 -13.1875 \r\n",
       "L 8.59375 -13.1875 \r\n",
       "z\r\n",
       "\" id=\"DejaVuSans-91\"/>\r\n",
       "     <path d=\"M 31.78125 66.40625 \r\n",
       "Q 24.171875 66.40625 20.328125 58.90625 \r\n",
       "Q 16.5 51.421875 16.5 36.375 \r\n",
       "Q 16.5 21.390625 20.328125 13.890625 \r\n",
       "Q 24.171875 6.390625 31.78125 6.390625 \r\n",
       "Q 39.453125 6.390625 43.28125 13.890625 \r\n",
       "Q 47.125 21.390625 47.125 36.375 \r\n",
       "Q 47.125 51.421875 43.28125 58.90625 \r\n",
       "Q 39.453125 66.40625 31.78125 66.40625 \r\n",
       "z\r\n",
       "M 31.78125 74.21875 \r\n",
       "Q 44.046875 74.21875 50.515625 64.515625 \r\n",
       "Q 56.984375 54.828125 56.984375 36.375 \r\n",
       "Q 56.984375 17.96875 50.515625 8.265625 \r\n",
       "Q 44.046875 -1.421875 31.78125 -1.421875 \r\n",
       "Q 19.53125 -1.421875 13.0625 8.265625 \r\n",
       "Q 6.59375 17.96875 6.59375 36.375 \r\n",
       "Q 6.59375 54.828125 13.0625 64.515625 \r\n",
       "Q 19.53125 74.21875 31.78125 74.21875 \r\n",
       "z\r\n",
       "\" id=\"DejaVuSans-48\"/>\r\n",
       "     <path d=\"M 30.421875 75.984375 \r\n",
       "L 30.421875 -13.1875 \r\n",
       "L 9.71875 -13.1875 \r\n",
       "L 9.71875 -6.203125 \r\n",
       "L 21.390625 -6.203125 \r\n",
       "L 21.390625 69 \r\n",
       "L 9.71875 69 \r\n",
       "L 9.71875 75.984375 \r\n",
       "z\r\n",
       "\" id=\"DejaVuSans-93\"/>\r\n",
       "    </defs>\r\n",
       "    <g transform=\"translate(18.4268 22.66001)scale(0.08 -0.08)\">\r\n",
       "     <use transform=\"translate(0 0.015625)\" xlink:href=\"#DejaVuSans-88\"/>\r\n",
       "     <use transform=\"translate(68.505859 0.015625)\" xlink:href=\"#DejaVuSans-91\"/>\r\n",
       "     <use transform=\"translate(107.519531 0.015625)\" xlink:href=\"#DejaVuSans-48\"/>\r\n",
       "     <use transform=\"translate(171.142578 0.015625)\" xlink:href=\"#DejaVuSans-93\"/>\r\n",
       "    </g>\r\n",
       "   </g>\r\n",
       "   <g id=\"text_2\">\r\n",
       "    <!-- $X[1]$ -->\r\n",
       "    <defs>\r\n",
       "     <path d=\"M 12.40625 8.296875 \r\n",
       "L 28.515625 8.296875 \r\n",
       "L 28.515625 63.921875 \r\n",
       "L 10.984375 60.40625 \r\n",
       "L 10.984375 69.390625 \r\n",
       "L 28.421875 72.90625 \r\n",
       "L 38.28125 72.90625 \r\n",
       "L 38.28125 8.296875 \r\n",
       "L 54.390625 8.296875 \r\n",
       "L 54.390625 0 \r\n",
       "L 12.40625 0 \r\n",
       "z\r\n",
       "\" id=\"DejaVuSans-49\"/>\r\n",
       "    </defs>\r\n",
       "    <g transform=\"translate(18.4268 132.82001)scale(0.08 -0.08)\">\r\n",
       "     <use transform=\"translate(0 0.015625)\" xlink:href=\"#DejaVuSans-88\"/>\r\n",
       "     <use transform=\"translate(68.505859 0.015625)\" xlink:href=\"#DejaVuSans-91\"/>\r\n",
       "     <use transform=\"translate(107.519531 0.015625)\" xlink:href=\"#DejaVuSans-49\"/>\r\n",
       "     <use transform=\"translate(171.142578 0.015625)\" xlink:href=\"#DejaVuSans-93\"/>\r\n",
       "    </g>\r\n",
       "   </g>\r\n",
       "   <g id=\"text_3\">\r\n",
       "    <!-- $Y[0]$ -->\r\n",
       "    <defs>\r\n",
       "     <path d=\"M -0.203125 72.90625 \r\n",
       "L 10.40625 72.90625 \r\n",
       "L 30.609375 42.921875 \r\n",
       "L 50.6875 72.90625 \r\n",
       "L 61.28125 72.90625 \r\n",
       "L 35.5 34.71875 \r\n",
       "L 35.5 0 \r\n",
       "L 25.59375 0 \r\n",
       "L 25.59375 34.71875 \r\n",
       "z\r\n",
       "\" id=\"DejaVuSans-89\"/>\r\n",
       "    </defs>\r\n",
       "    <g transform=\"translate(330.1308 83.853628)scale(0.08 -0.08)\">\r\n",
       "     <use transform=\"translate(0 0.015625)\" xlink:href=\"#DejaVuSans-89\"/>\r\n",
       "     <use transform=\"translate(61.083984 0.015625)\" xlink:href=\"#DejaVuSans-91\"/>\r\n",
       "     <use transform=\"translate(100.097656 0.015625)\" xlink:href=\"#DejaVuSans-48\"/>\r\n",
       "     <use transform=\"translate(163.720703 0.015625)\" xlink:href=\"#DejaVuSans-93\"/>\r\n",
       "    </g>\r\n",
       "   </g>\r\n",
       "  </g>\r\n",
       " </g>\r\n",
       " <defs>\r\n",
       "  <clipPath id=\"p6292f6e2f4\">\r\n",
       "   <rect height=\"152.73072\" width=\"338.0616\" x=\"7.2\" y=\"7.2\"/>\r\n",
       "  </clipPath>\r\n",
       " </defs>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<Figure size 375.624x179.683 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "def XOR2(a,b):\n",
    "    t  = NOT(AND(a,b))\n",
    "    u =  OR(a,b)\n",
    "    return AND(t,u)\n",
    "\n",
    "def XOR(X):\n",
    "    c = XOR2(X[0],X[1])\n",
    "    for i in range(2,len(X)):\n",
    "        c = XOR2(c,X[i])\n",
    "    return c\n",
    "\n",
    "circuit(XOR2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# circuit(XOR,10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "#for n in range(2,10):\n",
    "#    C = circuit(XOR,n)\n",
    "#    C.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import collections \n",
    "import inspect\n",
    "import re\n",
    "\n",
    "class QuitExecution(Exception):\n",
    "    pass\n",
    "\n",
    "class HaltExecution(Exception):\n",
    "    pass\n",
    "\n",
    "def extractstates(transition):\n",
    "    src = inspect.getsource(transition)\n",
    "    strings = re.findall( r'(?<!f)\"[a-zA-Z\\_0-9]*\"', src, re.I | re.M)\n",
    "    strings += re.findall( r\"(?<!f)'[a-zA-Z\\_0-9]*'\", src, re.I | re.M)\n",
    "    alphabet = [ \"▷\", \"·\",\"0\", \"1\" ]\n",
    "    states = [ \"START\"]\n",
    "    if src.find(\"boilerplate(\")>=0:\n",
    "        bpstates = [\"OUTPUT0\",\"OUTPUT1\",\"0ANDSTOP\",\"1ANDSTOP\"]\n",
    "    else: \n",
    "        bpstates = []\n",
    "    for s in strings:\n",
    "        t = s[1:-1]\n",
    "        if not t: continue\n",
    "        if len(t)>1:\n",
    "            if not t in states and not t in bpstates:\n",
    "                states.append(t)\n",
    "        else:\n",
    "            if not t in alphabet and not t in [\"L\",\"R\",\"H\",\"S\"]:\n",
    "                alphabet.append(t)\n",
    "    states += bpstates\n",
    "    return alphabet, states\n",
    "    \n",
    "class TuringMachine:\n",
    "   \n",
    "    def transition_table(self):\n",
    "    \n",
    "        T = {}\n",
    "        for i, s in enumerate(self.states):\n",
    "            for a in self.alphabet:\n",
    "                _s,_a,_m = self.transition(s,a)\n",
    "                T[(i,a)] = (self.states.index(_s),_a,_m)\n",
    "        return T\n",
    "        \n",
    "        \n",
    "        \n",
    "    def printtable(self,boiler=False):\n",
    "        header = [\"State\", \"Sym\", \"New State\", \"New Sym\", \"Move\"]\n",
    "        res = [header]\n",
    "        bpstates = [\"OUTPUT0\",\"OUTPUT1\",\"0ANDSTOP\",\"1ANDSTOP\"] if not boiler else []\n",
    "        skipped = False\n",
    "        for i, s in enumerate(self.states):\n",
    "            if s in bpstates: \n",
    "                skipped = True\n",
    "                continue\n",
    "            for a in self.alphabet:\n",
    "                s_, a_, m_ = self.transition(s,a)\n",
    "                res.append([f\"{i} ({s})\", a, s_, a_, m_ ])\n",
    "        if skipped: res.append([\"_boilerplate_\",\"...\",\"...\",\"...\",\"...\"])\n",
    "        display(mdtable(res))\n",
    "        \n",
    "    def _repr_pretty_(self, p, cycle):\n",
    "        if cycle: return \"cycle\"\n",
    "        self.printtable()\n",
    "        return None\n",
    "\n",
    "    def __init__(self, transition):\n",
    "        self.tape =  collections.defaultdict(lambda :\"·\")\n",
    "        self.tape[0] = \"▷\"\n",
    "        self.alphabet = [ \"▷\", \"·\",\"0\", \"1\" ]\n",
    "        self.transition = transition\n",
    "        self.head = 0\n",
    "        self.alphabet , self.states = extractstates(transition)\n",
    "        self.state = \"START\"\n",
    "        self.MAXSTEPS = 60\n",
    "        self.lenstate = max([len(s) for s in self.states])\n",
    "        self.history = []\n",
    "        \n",
    "    def input(self, x):\n",
    "        self.tape = [ \"▷\" ] + [str(a) for a in x ] + [ \"·\" ]\n",
    "        self.state = \"START\"\n",
    "        self.head = 0 \n",
    "    \n",
    "    def printstate(self):\n",
    "        tape_ = [self.tape[i] if i != self.head else myred(self.tape[i]) for i in range(len(self.tape))]\n",
    "        print(self.state.ljust(self.lenstate) + \" \"+ \"\".join(tape_))\n",
    "        return None\n",
    "    \n",
    "    \n",
    "    def next(self):\n",
    "        self.history.append((self.state, self.head, list(self.tape)))\n",
    "        self.state,self.tape[self.head],move = self.transition(self.state, self.tape[self.head])\n",
    "        if not self.state in self.states:\n",
    "            self.states.append(self.state)\n",
    "        if move==\"L\":\n",
    "            self.head = max(0, self.head-1)\n",
    "        if move ==\"R\":\n",
    "            self.head += 1\n",
    "            if self.head == len(self.tape):\n",
    "                self.tape.append(\"·\")\n",
    "        if move ==\"H\":\n",
    "            raise HaltExecution(\"Halted\")\n",
    "    \n",
    "    def prev(self):\n",
    "        if not self.history:\n",
    "            raise Exception(\"Can't go back - history is empty\")\n",
    "        self.state,self.head, self.tape = self.history.pop()\n",
    "        \n",
    "    def run(self,iterate = False, maxsteps = 0):\n",
    "        if iterate:\n",
    "            print(\"q(uit), n(ext),p(rev),c(lear),r(un),s(kip) XX\")\n",
    "        if not maxsteps:\n",
    "            maxsteps = self.MAXSTEPS\n",
    "        t = 0\n",
    "        noprinting = 0\n",
    "        quit_cmd = False\n",
    "        try:\n",
    "            while True:\n",
    "                if noprinting>0:\n",
    "                    noprinting -= 1\n",
    "                else:\n",
    "                    self.printstate()\n",
    "                if iterate and noprinting<=0:\n",
    "                    cmd = input(\"\")\n",
    "                    #CURSOR_UP_ONE = '\\x1b[1A'\n",
    "                    #ERASE_LINE = '\\x1b[2K'\n",
    "                    #print(CURSOR_UP_ONE + ERASE_LINE + CURSOR_UP_ONE)\n",
    "                    \n",
    "                    c = cmd[0] if cmd else \"n\"\n",
    "                    if c==\"c\":\n",
    "                        clear_output()\n",
    "                    elif c==\"r\":\n",
    "                        iterate = False\n",
    "                    elif c==\"s\":\n",
    "                        _,num = cmd.split(' ')\n",
    "                        print(\"...\")\n",
    "                        noprinting = int(num)\n",
    "                    elif c==\"p\":\n",
    "                        self.prev()\n",
    "                        t -= 1\n",
    "                        continue\n",
    "                    elif c==\"q\":\n",
    "                        raise QuitExecution(\"User quit\")\n",
    "                self.next()\n",
    "                if t >= maxsteps:\n",
    "                    raise Exception(\"Too many steps\")\n",
    "                t += 1\n",
    "               \n",
    "        except HaltExecution as e:\n",
    "            msg = str(e)\n",
    "            self.printstate()\n",
    "            y = \"\"\n",
    "            i = 1\n",
    "            while self.tape[i] != \"·\":\n",
    "                y += self.tape[i]\n",
    "                i += 1\n",
    "            return y\n",
    "        except  QuitExecution as e:\n",
    "            print(str(e))\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "__Q:__ Write Turing machine that computes $XOR:\\{0,1\\}^n \\rightarrow \\{0,1\\}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def xortm(state,sym):\n",
    "    move = \"R\"\n",
    "    if state==\"START\":\n",
    "        state = \"EVEN\"\n",
    "    elif state in [\"EVEN\",\"ODD\"]:\n",
    "        if sym== \"·\":\n",
    "            state = \"OUTPUT1\" if state==\"ODD\" else \"OUTPUT0\"\n",
    "            move  = \"L\"\n",
    "        elif sym==\"1\":\n",
    "            state = \"EVEN\" if state==\"ODD\" else \"ODD\"\n",
    "    else:\n",
    "        state,sym,move = boilerplate(state,sym)\n",
    "    return state,sym,move"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def boilerplate(state,sym):\n",
    "    move = \"H\"\n",
    "    if state in [\"OUTPUT1\",\"OUTPUT0\"]:\n",
    "        if sym != \"▷\":\n",
    "            move = \"L\"\n",
    "            sym= \"·\"\n",
    "        else:\n",
    "            move = \"R\"\n",
    "            state = state[-1]+\"ANDSTOP\"\n",
    "    elif state[1:] ==\"ANDSTOP\":\n",
    "        move = \"H\"\n",
    "        sym = state[0]\n",
    "    return state,sym,move\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "<B>State        </B> | <B>Sym          </B> | <B>New State    </B> | <B>New Sym      </B> | <B>Move         </B>\n",
       "--------------|--------------|--------------|--------------|--------------\n",
       "0 (START)     | ▷             | EVEN          | ▷             | R            \n",
       "0 (START)     | ·             | EVEN          | ·             | R            \n",
       "0 (START)     | 0             | EVEN          | 0             | R            \n",
       "0 (START)     | 1             | EVEN          | 1             | R            \n",
       "1 (EVEN)      | ▷             | EVEN          | ▷             | R            \n",
       "1 (EVEN)      | ·             | OUTPUT0       | ·             | L            \n",
       "1 (EVEN)      | 0             | EVEN          | 0             | R            \n",
       "1 (EVEN)      | 1             | ODD           | 1             | R            \n",
       "2 (ODD)       | ▷             | ODD           | ▷             | R            \n",
       "2 (ODD)       | ·             | OUTPUT1       | ·             | L            \n",
       "2 (ODD)       | 0             | ODD           | 0             | R            \n",
       "2 (ODD)       | 1             | EVEN          | 1             | R            \n",
       "_boilerplate_ | ...           | ...           | ...           | ...          \n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "MXOR = TuringMachine(xortm)\n",
    "MXOR.printtable(False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "START    \u001b[91m▷\u001b[0m1011·\n"
     ]
    }
   ],
   "source": [
    "MXOR.input(\"1011\")\n",
    "MXOR.printstate()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "START    \u001b[91m▷\u001b[0m1011·\n",
      "EVEN     ▷\u001b[91m1\u001b[0m011·\n",
      "ODD      ▷1\u001b[91m0\u001b[0m11·\n",
      "ODD      ▷10\u001b[91m1\u001b[0m1·\n",
      "EVEN     ▷101\u001b[91m1\u001b[0m·\n",
      "ODD      ▷1011\u001b[91m·\u001b[0m\n",
      "OUTPUT1  ▷101\u001b[91m1\u001b[0m·\n",
      "OUTPUT1  ▷10\u001b[91m1\u001b[0m··\n",
      "OUTPUT1  ▷1\u001b[91m0\u001b[0m···\n",
      "OUTPUT1  ▷\u001b[91m1\u001b[0m····\n",
      "OUTPUT1  \u001b[91m▷\u001b[0m·····\n",
      "1ANDSTOP ▷\u001b[91m·\u001b[0m····\n",
      "1ANDSTOP ▷\u001b[91m1\u001b[0m····\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'1'"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MXOR.run()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "__Q:__ Write a TM $M$ such that for every $x\\in \\{0,1\\}^n$, if $M$'s tape is initialized with $\\triangleright x_0 x_1 \\cdots x_{n-1} \\cdots$ then when it halts the tape is $\\triangleright PAL(x) \\cdots$ where $PAL(x)=1$ iff $x_i=x_{n-i}$ for every $i\\in [n]$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def palindrome(state,sym):\n",
    "    if sym== \"▷\" and state in [\"START\",\"SCANLEFT\"]:\n",
    "        state = \"LEFTMOST\"\n",
    "        move = \"R\"\n",
    "    elif state == \"LEFTMOST\":\n",
    "        if sym == \"·\":\n",
    "            state, move = \"OUTPUT1\",\"S\"\n",
    "        else:\n",
    "            state = \"LOOK0_SAW0\" if sym==\"0\" else \"LOOK1_SAW1\"\n",
    "            sym,move  = \"·\",\"R\"\n",
    "    elif state in [ \"LOOK0_SAW0\", \"LOOK0_SAW1\", \"LOOK1_SAW0\", \"LOOK1_SAW1\" ]:\n",
    "        if sym == \"▷\":\n",
    "            move = \"H\"\n",
    "        elif sym == \"·\":\n",
    "            state = \"OUTPUT0\" if state[4] != state[9] else \"ERASE\"\n",
    "            move  = \"L\"\n",
    "        else:\n",
    "            state, move = state[:-1]+sym, \"R\"\n",
    "    elif state == \"ERASE\":\n",
    "        if sym == \"·\":\n",
    "            state,move = \"LEFTMOST\",\"R\"\n",
    "        else:\n",
    "            state,sym,move = \"SCANLEFT\", \"·\", \"L\"\n",
    "    elif state == \"SCANLEFT\":\n",
    "        if sym == \"·\":\n",
    "            state,move = \"LEFTMOST\",\"R\"\n",
    "        else:\n",
    "            move = \"L\"\n",
    "    else:\n",
    "        state,sym,move = boilerplate(state,sym)\n",
    "    return state,sym,move"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "<B>State         </B> | <B>Sym           </B> | <B>New State     </B> | <B>New Sym       </B> | <B>Move          </B>\n",
       "---------------|---------------|---------------|---------------|---------------\n",
       "0 (START)      | ▷              | LEFTMOST       | ▷              | R             \n",
       "0 (START)      | ·              | START          | ·              | H             \n",
       "0 (START)      | 0              | START          | 0              | H             \n",
       "0 (START)      | 1              | START          | 1              | H             \n",
       "1 (SCANLEFT)   | ▷              | LEFTMOST       | ▷              | R             \n",
       "1 (SCANLEFT)   | ·              | LEFTMOST       | ·              | R             \n",
       "1 (SCANLEFT)   | 0              | SCANLEFT       | 0              | L             \n",
       "1 (SCANLEFT)   | 1              | SCANLEFT       | 1              | L             \n",
       "2 (LEFTMOST)   | ▷              | LOOK1_SAW1     | ·              | R             \n",
       "2 (LEFTMOST)   | ·              | OUTPUT1        | ·              | S             \n",
       "2 (LEFTMOST)   | 0              | LOOK0_SAW0     | ·              | R             \n",
       "2 (LEFTMOST)   | 1              | LOOK1_SAW1     | ·              | R             \n",
       "3 (LOOK0_SAW0) | ▷              | LOOK0_SAW0     | ▷              | H             \n",
       "3 (LOOK0_SAW0) | ·              | ERASE          | ·              | L             \n",
       "3 (LOOK0_SAW0) | 0              | LOOK0_SAW0     | 0              | R             \n",
       "3 (LOOK0_SAW0) | 1              | LOOK0_SAW1     | 1              | R             \n",
       "4 (LOOK1_SAW1) | ▷              | LOOK1_SAW1     | ▷              | H             \n",
       "4 (LOOK1_SAW1) | ·              | ERASE          | ·              | L             \n",
       "4 (LOOK1_SAW1) | 0              | LOOK1_SAW0     | 0              | R             \n",
       "4 (LOOK1_SAW1) | 1              | LOOK1_SAW1     | 1              | R             \n",
       "5 (LOOK0_SAW1) | ▷              | LOOK0_SAW1     | ▷              | H             \n",
       "5 (LOOK0_SAW1) | ·              | OUTPUT0        | ·              | L             \n",
       "5 (LOOK0_SAW1) | 0              | LOOK0_SAW0     | 0              | R             \n",
       "5 (LOOK0_SAW1) | 1              | LOOK0_SAW1     | 1              | R             \n",
       "6 (LOOK1_SAW0) | ▷              | LOOK1_SAW0     | ▷              | H             \n",
       "6 (LOOK1_SAW0) | ·              | OUTPUT0        | ·              | L             \n",
       "6 (LOOK1_SAW0) | 0              | LOOK1_SAW0     | 0              | R             \n",
       "6 (LOOK1_SAW0) | 1              | LOOK1_SAW1     | 1              | R             \n",
       "7 (ERASE)      | ▷              | SCANLEFT       | ·              | L             \n",
       "7 (ERASE)      | ·              | LEFTMOST       | ·              | R             \n",
       "7 (ERASE)      | 0              | SCANLEFT       | ·              | L             \n",
       "7 (ERASE)      | 1              | SCANLEFT       | ·              | L             \n",
       "_boilerplate_  | ...            | ...            | ...            | ...           \n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": []
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "PalM = TuringMachine(palindrome)\n",
    "PalM"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "START      \u001b[91m▷\u001b[0m11001·\n"
     ]
    }
   ],
   "source": [
    "PalM.input(\"11001\")\n",
    "PalM.printstate()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "START      \u001b[91m▷\u001b[0m11001·\n",
      "LEFTMOST   ▷\u001b[91m1\u001b[0m1001·\n",
      "LOOK1_SAW1 ▷·\u001b[91m1\u001b[0m001·\n",
      "LOOK1_SAW1 ▷·1\u001b[91m0\u001b[0m01·\n",
      "LOOK1_SAW0 ▷·10\u001b[91m0\u001b[0m1·\n",
      "LOOK1_SAW0 ▷·100\u001b[91m1\u001b[0m·\n",
      "LOOK1_SAW1 ▷·1001\u001b[91m·\u001b[0m\n",
      "ERASE      ▷·100\u001b[91m1\u001b[0m·\n",
      "SCANLEFT   ▷·10\u001b[91m0\u001b[0m··\n",
      "SCANLEFT   ▷·1\u001b[91m0\u001b[0m0··\n",
      "SCANLEFT   ▷·\u001b[91m1\u001b[0m00··\n",
      "SCANLEFT   ▷\u001b[91m·\u001b[0m100··\n",
      "LEFTMOST   ▷·\u001b[91m1\u001b[0m00··\n",
      "LOOK1_SAW1 ▷··\u001b[91m0\u001b[0m0··\n",
      "LOOK1_SAW0 ▷··0\u001b[91m0\u001b[0m··\n",
      "LOOK1_SAW0 ▷··00\u001b[91m·\u001b[0m·\n",
      "OUTPUT0    ▷··0\u001b[91m0\u001b[0m··\n",
      "OUTPUT0    ▷··\u001b[91m0\u001b[0m···\n",
      "OUTPUT0    ▷·\u001b[91m·\u001b[0m····\n",
      "OUTPUT0    ▷\u001b[91m·\u001b[0m·····\n",
      "OUTPUT0    \u001b[91m▷\u001b[0m······\n",
      "0ANDSTOP   ▷\u001b[91m·\u001b[0m·····\n",
      "0ANDSTOP   ▷\u001b[91m0\u001b[0m·····\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'0'"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "PalM.run()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(0, '▷'): (2, '▷', 'R'),\n",
       " (0, '·'): (0, '·', 'H'),\n",
       " (0, '0'): (0, '0', 'H'),\n",
       " (0, '1'): (0, '1', 'H'),\n",
       " (1, '▷'): (2, '▷', 'R'),\n",
       " (1, '·'): (2, '·', 'R'),\n",
       " (1, '0'): (1, '0', 'L'),\n",
       " (1, '1'): (1, '1', 'L'),\n",
       " (2, '▷'): (4, '·', 'R'),\n",
       " (2, '·'): (9, '·', 'S'),\n",
       " (2, '0'): (3, '·', 'R'),\n",
       " (2, '1'): (4, '·', 'R'),\n",
       " (3, '▷'): (3, '▷', 'H'),\n",
       " (3, '·'): (7, '·', 'L'),\n",
       " (3, '0'): (3, '0', 'R'),\n",
       " (3, '1'): (5, '1', 'R'),\n",
       " (4, '▷'): (4, '▷', 'H'),\n",
       " (4, '·'): (7, '·', 'L'),\n",
       " (4, '0'): (6, '0', 'R'),\n",
       " (4, '1'): (4, '1', 'R'),\n",
       " (5, '▷'): (5, '▷', 'H'),\n",
       " (5, '·'): (8, '·', 'L'),\n",
       " (5, '0'): (3, '0', 'R'),\n",
       " (5, '1'): (5, '1', 'R'),\n",
       " (6, '▷'): (6, '▷', 'H'),\n",
       " (6, '·'): (8, '·', 'L'),\n",
       " (6, '0'): (6, '0', 'R'),\n",
       " (6, '1'): (4, '1', 'R'),\n",
       " (7, '▷'): (1, '·', 'L'),\n",
       " (7, '·'): (2, '·', 'R'),\n",
       " (7, '0'): (1, '·', 'L'),\n",
       " (7, '1'): (1, '·', 'L'),\n",
       " (8, '▷'): (10, '▷', 'R'),\n",
       " (8, '·'): (8, '·', 'L'),\n",
       " (8, '0'): (8, '·', 'L'),\n",
       " (8, '1'): (8, '·', 'L'),\n",
       " (9, '▷'): (11, '▷', 'R'),\n",
       " (9, '·'): (9, '·', 'L'),\n",
       " (9, '0'): (9, '·', 'L'),\n",
       " (9, '1'): (9, '·', 'L'),\n",
       " (10, '▷'): (10, '0', 'H'),\n",
       " (10, '·'): (10, '0', 'H'),\n",
       " (10, '0'): (10, '0', 'H'),\n",
       " (10, '1'): (10, '0', 'H'),\n",
       " (11, '▷'): (11, '1', 'H'),\n",
       " (11, '·'): (11, '1', 'H'),\n",
       " (11, '0'): (11, '1', 'H'),\n",
       " (11, '1'): (11, '1', 'H')}"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "PalM.transition_table()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Evaluating TMs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Use "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def EVAL(δ,x):\n",
    "    Tape = [\"▷\"] + [a for a in x]\n",
    "    i = 0; s = 0 \n",
    "    while True:\n",
    "        s, Tape[i], d = δ[(s,Tape[i])] \n",
    "        if d == \"H\": break\n",
    "        if d == \"L\": i = max(i-1,0)\n",
    "        if d == \"R\": i += 1\n",
    "        if i>= len(Tape): Tape.append('Φ')\n",
    "    return Tape[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "def EVAL(δ,x): \n",
    "    '''Evaluate TM given by transition table δ \n",
    "    on input x'''\n",
    "    Tape = [\"▷\"] + [a for a in x]\n",
    "    i = 0; s = 0 # i = head pos, s = state\n",
    "    while True:\n",
    "        s, Tape[i], d = δ[(s,Tape[i])] \n",
    "        if d == \"H\": break\n",
    "        if d == \"L\": i = max(i-1,0)\n",
    "        if d == \"R\": i += 1\n",
    "        if i>= len(Tape): Tape.append('Φ')\n",
    "            \n",
    "    j = 1; Y = [] # produce output\n",
    "    while Tape[j] != 'Φ': \n",
    "        Y.append(Tape[j])\n",
    "        j += 1\n",
    "    return Y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "ename": "KeyError",
     "evalue": "(4, 'Φ')",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mKeyError\u001b[0m                                  Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-20-9cf2a13db4d5>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mEVAL\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mPalM\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mtransition_table\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;34m\"11011\"\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m<ipython-input-19-37e68b495e59>\u001b[0m in \u001b[0;36mEVAL\u001b[1;34m(δ, x)\u001b[0m\n\u001b[0;32m      5\u001b[0m     \u001b[0mi\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;36m0\u001b[0m\u001b[1;33m;\u001b[0m \u001b[0ms\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;36m0\u001b[0m \u001b[1;31m# i = head pos, s = state\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      6\u001b[0m     \u001b[1;32mwhile\u001b[0m \u001b[1;32mTrue\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 7\u001b[1;33m         \u001b[0ms\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mTape\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0md\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mδ\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0ms\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mTape\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      8\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0md\u001b[0m \u001b[1;33m==\u001b[0m \u001b[1;34m\"H\"\u001b[0m\u001b[1;33m:\u001b[0m \u001b[1;32mbreak\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      9\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0md\u001b[0m \u001b[1;33m==\u001b[0m \u001b[1;34m\"L\"\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mi\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mmax\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mKeyError\u001b[0m: (4, 'Φ')"
     ]
    }
   ],
   "source": [
    "EVAL(PalM.transition_table(),\"11011\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## NAND-TM"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "def extractvars(src):\n",
    "    varnames = re.findall( r'(?<!f)[a-zA-Z\\_0-9]+', src, re.I | re.M)\n",
    "    arrays = [\"X\",\"X_nonblank\",\"Y\",\"Y_nonblank\"]\n",
    "    scalars = []\n",
    "    for t in varnames:\n",
    "        if t in ['i','0','1'] or t=='NAND': continue\n",
    "        if t[0].isupper():\n",
    "            if not t in arrays: arrays.append(t)\n",
    "        else:\n",
    "            if not t in scalars: scalars.append(t)\n",
    "    return scalars, arrays\n",
    "    \n",
    "class NANDTM:\n",
    "   \n",
    "        \n",
    "    def _repr_pretty_(self, p, cycle):\n",
    "        if cycle: return \"cycle\"\n",
    "        print (self.source)\n",
    "        \n",
    "    def __init__(self, source):\n",
    "        self.source = [l for l in source.split('\\n') if l]\n",
    "        self.scalars , self.arrays  =  extractvars(source)\n",
    "        self.vals = collections.defaultdict(int)\n",
    "        self.i = 0\n",
    "        self.pc = 0\n",
    "        self.maxlen = 1\n",
    "        self.namelen = max([len(a) for a in self.scalars]+[len(a) for a in self.arrays])\n",
    "        self.MAXSTEPS = 50\n",
    "        self.modified = ()\n",
    "        \n",
    "    def getval(self,varname, i = 0):\n",
    "        return self.vals[(varname,i)]\n",
    "        \n",
    "    def setval(self,varname,i,val):\n",
    "        self.vals[(varname,i)] = val\n",
    "        \n",
    "    \n",
    "    def input(self, x):\n",
    "        for i,a in enumerate(x):\n",
    "            self.setval(\"X\",i,int(a))\n",
    "            self.setval(\"X_nonblank\",i,1)\n",
    "        self.pc = 0\n",
    "        self.i = 0\n",
    "        self.maxlen = len(x)\n",
    "    \n",
    "    def modifiedvar(self):\n",
    "        line = self.source[self.pc]\n",
    "        if line[:9] == \"MODANDJMP\": return (\"_\",0)\n",
    "        foo, op, bar, blah = parseline(line)\n",
    "        if foo[-1]==']':\n",
    "            j = foo.find(\"[\")\n",
    "            name_ = foo[:j]\n",
    "            i_    = self.i if foo[j+1]=='i' else int(foo[j+1:-1])\n",
    "        else:\n",
    "            name_ = foo\n",
    "            i_ = 0\n",
    "        return name_,i_\n",
    "    \n",
    "    def printstate(self):\n",
    "        res = \"\"\n",
    "        def arrvals(name):\n",
    "            def v(name,i):\n",
    "                name_,i_ = self.modifiedvar()\n",
    "                a = str(self.getval(name,i))\n",
    "                if (name_,i_)==(name,i):\n",
    "                    return mygreen(a)\n",
    "                if self.i == i:\n",
    "                    return myred(a)\n",
    "                return a\n",
    "            return \"\".join([v(name,i) for i in range(self.maxlen) ])\n",
    "        name_,i_ = self.modifiedvar()\n",
    "        \n",
    "        for a in self.arrays:\n",
    "            b = mygreen(a.ljust(self.namelen)) if a==name_ else a.ljust(self.namelen)\n",
    "            res += b + \": \"+ arrvals(a)+\"\\n\"\n",
    "        for a in self.scalars:\n",
    "            b = mygreen(a.ljust(self.namelen)) if a==name_ else a.ljust(self.namelen)\n",
    "            res += b + \": \"+ str(self.getval(a))+\"\\n\"\n",
    "        res += \"\\n\"\n",
    "        for p,l in enumerate(self.source):\n",
    "            if p == self.pc:\n",
    "                l = myred(l)\n",
    "            res += l+\"\\n\"\n",
    "        print(res)\n",
    "    \n",
    "    \n",
    "    def next(self,printstate = False):\n",
    "        def pname(foo):\n",
    "            if foo[-1]==']':\n",
    "                j = foo.find(\"[\")\n",
    "                name = foo[:j]\n",
    "                i    = self.i if foo[j+1]=='i' else int(foo[j+1:-1])\n",
    "            else:\n",
    "                name = foo\n",
    "                i = 0\n",
    "            return name,i\n",
    "        \n",
    "        line = self.source[self.pc]\n",
    "        if line[:9] == \"MODANDJMP\":\n",
    "            j = line.find(\"(\")\n",
    "            k = line.find(\",\")\n",
    "            l = line.find(\")\")\n",
    "            a = self.getval(*pname(line[j+1:k].strip()))\n",
    "            b = self.getval(*pname(line[k+1:l].strip()))\n",
    "            if printstate:\n",
    "                clear_output()\n",
    "                self.printstate()\n",
    "            if not a and not b: raise HaltExecution(\"halted\")\n",
    "            if b:\n",
    "                if a: self.i += 1\n",
    "                else: self.i = max(0,self.i-1)\n",
    "            self.pc = 0\n",
    "            self.maxlen = max(self.maxlen, self.i+1)\n",
    "            return\n",
    "        foo, op, bar, blah = parseline(line)\n",
    "        a = self.getval(*pname(bar))\n",
    "        b = self.getval(*pname(blah))\n",
    "        self.setval(*pname(foo),1-a*b)\n",
    "        self.pc = self.pc + 1 \n",
    "        if printstate:\n",
    "            clear_output()\n",
    "            self.printstate()\n",
    "    \n",
    "    def run(self,iterate = False, maxsteps = 0):\n",
    "        if iterate:\n",
    "            print(\"q(uit), n(ext),p(rev),c(lear),r(un),s(kip) XX\")\n",
    "        if not maxsteps:\n",
    "            maxsteps = self.MAXSTEPS\n",
    "        t = 0\n",
    "        noprinting = 0\n",
    "        quit_cmd = False\n",
    "        try:\n",
    "            while True:\n",
    "                if noprinting>0:\n",
    "                    noprinting -= 1\n",
    "                else:\n",
    "                    clear_output()\n",
    "                    self.printstate()\n",
    "                if iterate and noprinting<=0:\n",
    "                    cmd = input(\"\")\n",
    "                    #CURSOR_UP_ONE = '\\x1b[1A'\n",
    "                    #ERASE_LINE = '\\x1b[2K'\n",
    "                    #print(CURSOR_UP_ONE + ERASE_LINE + CURSOR_UP_ONE)\n",
    "                    \n",
    "                    c = cmd[0] if cmd else \"n\"\n",
    "                    if c==\"c\":\n",
    "                        clear_output()\n",
    "                    elif c==\"r\":\n",
    "                        iterate = False\n",
    "                    elif c==\"s\":\n",
    "                        _,num = cmd.split(' ')\n",
    "                        print(\"...\")\n",
    "                        noprinting = int(num)\n",
    "                    elif c==\"p\":\n",
    "                        self.prev()\n",
    "                        t -= 1\n",
    "                        continue\n",
    "                    elif c==\"q\":\n",
    "                        raise QuitExecution(\"User quit\")\n",
    "                self.next()\n",
    "                if t >= maxsteps:\n",
    "                    raise Exception(\"Too many steps\")\n",
    "                t += 1\n",
    "               \n",
    "        except HaltExecution as e:\n",
    "            msg = str(e)\n",
    "            clear_output()\n",
    "            self.printstate()\n",
    "            y = \"\"\n",
    "            i = 0\n",
    "            while self.getval(\"Y_nonblank\",i) :\n",
    "                y += str(self.getval(\"Y\",i))\n",
    "                i += 1\n",
    "            return y\n",
    "        except  QuitExecution as e:\n",
    "            print(str(e))\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "source = r'''temp_0 = NAND(X[0],X[0])\n",
    "Y_nonblank[0] = NAND(X[0],temp_0)\n",
    "temp_2 = NAND(X[i],Y[0])\n",
    "temp_3 = NAND(X[i],temp_2)\n",
    "temp_4 = NAND(Y[0],temp_2)\n",
    "Y[0] = NAND(temp_3,temp_4)\n",
    "MODANDJMP(X_nonblank[i],X_nonblank[i])'''\n",
    "\n",
    "xorprog = NANDTM(source)\n",
    "xorprog.input(\"111\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X         : \u001b[91m1\u001b[0m11\n",
      "X_nonblank: \u001b[91m1\u001b[0m11\n",
      "Y         : \u001b[91m0\u001b[0m00\n",
      "Y_nonblank: \u001b[91m0\u001b[0m00\n",
      "MODANDJMP : \u001b[91m0\u001b[0m00\n",
      "\u001b[32mtemp_0    \u001b[0m: 0\n",
      "temp_2    : 0\n",
      "temp_3    : 0\n",
      "temp_4    : 0\n",
      "\n",
      "\u001b[91mtemp_0 = NAND(X[0],X[0])\u001b[0m\n",
      "Y_nonblank[0] = NAND(X[0],temp_0)\n",
      "temp_2 = NAND(X[i],Y[0])\n",
      "temp_3 = NAND(X[i],temp_2)\n",
      "temp_4 = NAND(Y[0],temp_2)\n",
      "Y[0] = NAND(temp_3,temp_4)\n",
      "MODANDJMP(X_nonblank[i],X_nonblank[i])\n",
      "\n"
     ]
    }
   ],
   "source": [
    "xorprog.printstate()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X         : \u001b[91m1\u001b[0m011\n",
      "X_nonblank: \u001b[91m1\u001b[0m111\n",
      "Y         : \u001b[91m0\u001b[0m000\n",
      "Y_nonblank: \u001b[91m0\u001b[0m000\n",
      "MODANDJMP : \u001b[91m0\u001b[0m000\n",
      "\u001b[32mtemp_0    \u001b[0m: 0\n",
      "temp_2    : 0\n",
      "temp_3    : 0\n",
      "temp_4    : 0\n",
      "\n",
      "\u001b[91mtemp_0 = NAND(X[0],X[0])\u001b[0m\n",
      "Y_nonblank[0] = NAND(X[0],temp_0)\n",
      "temp_2 = NAND(X[i],Y[0])\n",
      "temp_3 = NAND(X[i],temp_2)\n",
      "temp_4 = NAND(Y[0],temp_2)\n",
      "Y[0] = NAND(temp_3,temp_4)\n",
      "MODANDJMP(X_nonblank[i],X_nonblank[i])\n",
      "\n"
     ]
    }
   ],
   "source": [
    "xorprog.input(\"1011\")\n",
    "xorprog.printstate()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X         : 1011\u001b[91m0\u001b[0m\n",
      "X_nonblank: 1111\u001b[91m0\u001b[0m\n",
      "Y         : 1000\u001b[91m0\u001b[0m\n",
      "Y_nonblank: 1000\u001b[91m0\u001b[0m\n",
      "MODANDJMP : 0000\u001b[91m0\u001b[0m\n",
      "temp_0    : 0\n",
      "temp_2    : 1\n",
      "temp_3    : 1\n",
      "temp_4    : 0\n",
      "\n",
      "temp_0 = NAND(X[0],X[0])\n",
      "Y_nonblank[0] = NAND(X[0],temp_0)\n",
      "temp_2 = NAND(X[i],Y[0])\n",
      "temp_3 = NAND(X[i],temp_2)\n",
      "temp_4 = NAND(Y[0],temp_2)\n",
      "Y[0] = NAND(temp_3,temp_4)\n",
      "\u001b[91mMODANDJMP(X_nonblank[i],X_nonblank[i])\u001b[0m\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'1'"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "xorprog.run(False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X         : 1111\u001b[91m0\u001b[0m\n",
      "X_nonblank: 1111\u001b[91m0\u001b[0m\n",
      "Y         : 1000\u001b[91m0\u001b[0m\n",
      "Y_nonblank: 1000\u001b[91m0\u001b[0m\n",
      "MODANDJMP : 0000\u001b[91m0\u001b[0m\n",
      "temp_0    : 0\n",
      "temp_2    : 1\n",
      "temp_3    : 1\n",
      "temp_4    : 0\n",
      "\n",
      "temp_0 = NAND(X[0],X[0])\n",
      "Y_nonblank[0] = NAND(X[0],temp_0)\n",
      "temp_2 = NAND(X[i],Y[0])\n",
      "temp_3 = NAND(X[i],temp_2)\n",
      "temp_4 = NAND(Y[0],temp_2)\n",
      "Y[0] = NAND(temp_3,temp_4)\n",
      "\u001b[91mMODANDJMP(X_nonblank[i],X_nonblank[i])\u001b[0m\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'1'"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "xorprog.input(\"111\")\n",
    "xorprog.run(False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X         : 1111\u001b[91m0\u001b[0m\n",
      "X_nonblank: 1111\u001b[91m0\u001b[0m\n",
      "Y         : 1000\u001b[91m0\u001b[0m\n",
      "Y_nonblank: 1000\u001b[91m0\u001b[0m\n",
      "MODANDJMP : 0000\u001b[91m0\u001b[0m\n",
      "temp_0    : 0\n",
      "temp_2    : 1\n",
      "temp_3    : 1\n",
      "temp_4    : 0\n",
      "\n",
      "temp_0 = NAND(X[0],X[0])\n",
      "Y_nonblank[0] = NAND(X[0],temp_0)\n",
      "temp_2 = NAND(X[i],Y[0])\n",
      "temp_3 = NAND(X[i],temp_2)\n",
      "temp_4 = NAND(Y[0],temp_2)\n",
      "Y[0] = NAND(temp_3,temp_4)\n",
      "\u001b[91mMODANDJMP(X_nonblank[i],X_nonblank[i])\u001b[0m\n",
      "\n"
     ]
    },
    {
     "ename": "HaltExecution",
     "evalue": "halted",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mHaltExecution\u001b[0m                             Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-27-b2105633b4fe>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mxorprog\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mnext\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;32mTrue\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m<ipython-input-21-057aa62c7dfc>\u001b[0m in \u001b[0;36mnext\u001b[1;34m(self, printstate)\u001b[0m\n\u001b[0;32m    108\u001b[0m                 \u001b[0mclear_output\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    109\u001b[0m                 \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mprintstate\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 110\u001b[1;33m             \u001b[1;32mif\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[0ma\u001b[0m \u001b[1;32mand\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[0mb\u001b[0m\u001b[1;33m:\u001b[0m \u001b[1;32mraise\u001b[0m \u001b[0mHaltExecution\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"halted\"\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    111\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[0mb\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    112\u001b[0m                 \u001b[1;32mif\u001b[0m \u001b[0ma\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mi\u001b[0m \u001b[1;33m+=\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mHaltExecution\u001b[0m: halted"
     ]
    }
   ],
   "source": [
    "xorprog.next(True)"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "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.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}