Fall23_Lec6_loops.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>\n",
       ".rise-enabled .cell .input_prompt {\n",
       "    display: none;\n",
       "}\n",
       "</style>\n",
       "<!--- <style>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%html\n",
    "<style>\n",
    ".rise-enabled .cell .input_prompt {\n",
    "    display: none;\n",
    "}\n",
    "</style>\n",
    "<!--- <style>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# CS 121 Lecture 6 : Turing Machines and Loops"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "## Utilities\n",
    "(Ignore at first read)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "from IPython.display import Markdown, Math, display, clear_output\n",
    "import time\n",
    "\n",
    "def htmlspace(s):\n",
    "    return s.replace(\" \",\"&nbsp;\")\n",
    "\n",
    "def printmd(string, color=None):\n",
    "    colorstr = \"<span style='color:{}'>{}</span>\".format(color, string) if color else string\n",
    "    display(Markdown(colorstr))\n",
    "    \n",
    "def color(c,s,j=0):\n",
    "    return \"<span style='color:{}'>{}</span>\".format(c, s.ljust(j))\n",
    "    \n",
    "def bold(s,justify=0):\n",
    "    return (\"**\"+s+\"**\").ljust(justify)\n",
    "#  return \"\\x1b[1m\"+s.ljust(justify)+\"\\x1b[0m\"\n",
    "\n",
    "#def underline(s,justify=0):\n",
    "#    return \"\\x1b[4m\"+s.ljust(justify)+\"\\x1b[24m\"\n",
    "\n",
    "def red(s,justify=0):\n",
    "    return color(\"red\",s,justify)  #.replace(\" \",\"&nbsp;\")\n",
    "    #return  \"\\x1b[31m\"+s.ljust(justify)+\"\\x1b[0m\"\n",
    "\n",
    "\n",
    "def green(s,justify=0):\n",
    "    return color(\"green\",s,justify) #.replace(\" \",\"&nbsp;\")\n",
    "    # return  \"\\x1b[32m\"+s.ljust(justify)+\"\\x1b[0m\"\n",
    "\n",
    "\n",
    "def blue(s,justify=0):\n",
    "    return color(\"blue\",s,justify) #.replace(\" \",\"&nbsp;\")\n",
    "    # return  \"\\x1b[34m\"+s.ljust(justify)+\"\\x1b[0m\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "from IPython.display import HTML\n",
    "def mdtable(L,header=True):\n",
    "    l = max(max([len(str(a)) for a in A]) for A in L)+5\n",
    "    n = len(L[0])\n",
    "    res = \"\"\n",
    "    sep = \"|-\".join([\"-\"*(l+1) for i in range(n)])+\"\\n\"\n",
    "    for A in L:\n",
    "        res += \" | \".join([bold(str(s),l) if header else str(s).ljust(l) for s in A])+\"\\n\"\n",
    "        if header:\n",
    "            res += sep\n",
    "            header = False\n",
    "    return Markdown(res)\n",
    "\n",
    "def htmltable(L,header=True, thicker=100):\n",
    "    l = max(max([len(str(a)) for a in A]) for A in L)+5\n",
    "    n = len(L[0])\n",
    "    res=\"\"\"<style>\n",
    ".table-bordered {\n",
    "    border-collapse: collapse;\n",
    "}\n",
    ".table-bordered th, .table-bordered td {\n",
    "    border: 1px solid black;\n",
    "    padding: 5px;\n",
    "    text-align: left !important;\n",
    "}\n",
    "\n",
    ".table-bordered th:nth-child(ZZZ), .table-bordered td:nth-child(ZZZ) {\n",
    "    border-right: 3px solid black;\n",
    "}\n",
    ".table-bordered th {\n",
    "    border-bottom: 3px solid black !important;\n",
    "}\n",
    "</style>\n",
    "<table class=\"table-bordered\">\n",
    "\"\"\".replace(\"ZZZ\",str(thicker))\n",
    "    res += \"<thead>\\n\" if header else \"<tbody>\"\n",
    "    def wrap(i,x):\n",
    "        if i==0 and header: return f\"<th>{x}</th>\"\n",
    "        return f\"<td>{x}</td>\"\n",
    "    for i,A in enumerate(L):\n",
    "        res += \"<tr>\\n\" + \"\\n\".join([wrap(i,x) for x in A]) +\"\\n</tr>\"\n",
    "        if i==0 and header: res += \"\\n</thead><tbody>\\n\"\n",
    "    res += \"\\n</tbody><table>\"\n",
    "    return HTML(res)\n",
    "\n",
    "\n",
    "#L = [[\"col one\", \"col 2\", \"col 3\"],[2, 18, 19], [4, 20, 23]]\n",
    "#mdtable(L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "tags": []
   },
   "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": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "import collections\n",
    "from collections import defaultdict\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",
    "    states = [s for s in states if s != 'ANDSTOP']\n",
    "    return alphabet, states\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "## Actual lecture"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "__Q:__ Write Turing machine that computes $XOR:\\{0,1\\}^* \\rightarrow \\{0,1\\}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "__Solution:__ The machine will have a state `EVEN` and `ODD` keeping track of whether so far it has seen an even or odd number of $1$'s. \n",
    "When it reaches the end, depending on which state it's in, it will move to either `OUTPUT0` or `OUTPUT1` states, which will cause it to move to the leftmost and output $0$ or $1$ respectivly.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "def xortm(state,sym):\n",
    "    # transition function for XOR Turing Machine\n",
    "    move = \"R\"\n",
    "    if state==\"START\":  state = \"EVEN\"\n",
    "    elif state in [\"EVEN\",\"ODD\"]:\n",
    "        if sym==\"1\":\n",
    "            # flip state if we see a 1\n",
    "            state = \"EVEN\" if state==\"ODD\" else \"ODD\"\n",
    "        elif sym== \"∅\":\n",
    "            # at end of tape decide on output based on parity\n",
    "            state = \"OUTPUT1\" if state==\"ODD\" else \"OUTPUT0\"\n",
    "            move  = \"L\"\n",
    "    # boilerplate\n",
    "    elif state in [\"OUTPUT1\",\"OUTPUT0\"]:\n",
    "        if sym != \"▷\":\n",
    "            move, sym  = \"L\", \"∅\"\n",
    "        else:\n",
    "            move, state = \"R\" , state[-1]+\"ANDSTOP\"\n",
    "    elif state[1:] ==\"ANDSTOP\":\n",
    "        move, sym = \"H\", state[0]   \n",
    "    return state,sym,move"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "class TuringMachine:\n",
    "   \n",
    "    def __init__(self, transition):\n",
    "        self.alphabet = [ \"▷\", \"∅\",\"0\", \"1\" ] \n",
    "        self.transition = transition\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 run(self):\n",
    "        while True:\n",
    "            self.state, self.tape[self.head] , move = self.transition(\n",
    "                                                           self.state, self.tape[self.head] )\n",
    "            \n",
    "            if move==\"L\": self.head = max(0, self.head-1)\n",
    "            if move==\"R\":self.head += 1\n",
    "            if move==\"H\": break\n",
    "            if self.head >= len(self.tape): \n",
    "                self.tape.append(\"∅\")\n",
    "        return self.tape[1]  # more generally, all positions until first \"∅\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1'"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MXOR = TuringMachine(xortm)\n",
    "MXOR.input([0,1,1,1,0,0,1,1,0,0])\n",
    "MXOR.run()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "class TuringMachine:\n",
    "    \"\"\"Fancier version with better printing etc...\"\"\"\n",
    "   \n",
    "    def printtable(self,boiler=False):\n",
    "\n",
    "        header = [\"Curr State\", \"Curr Sym\", \"New State\", \"New Sym\", \"Move\"]\n",
    "        res = [header]\n",
    "        bpstates = [\"OUTPUT0\",\"OUTPUT1\",\"0ANDSTOP\",\"1ANDSTOP\", \"ANDSTOP\"] 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",
    "            first_sym = True\n",
    "            for a in self.alphabet:\n",
    "                s_, a_, m_ = self.transition(s,a)\n",
    "                if first_sym:\n",
    "                    res.append([f\"{i} ({s})\", a, s_, a_, m_ ])\n",
    "                    first_sym = False\n",
    "                else:\n",
    "                    res.append([\"--\", a, s_, a_, m_ ])\n",
    "                    \n",
    "        if skipped: res.append([\"_boilerplate_\",\"...\",\"...\",\"...\",\"...\"])\n",
    "        \n",
    "        display(htmltable(res,header=True,thicker=2))\n",
    "        \n",
    "        \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.print_history = \"\"\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])+2\n",
    "        self.history = []\n",
    "        \n",
    "    def input(self, x):\n",
    "        self.print_history = \"\"\n",
    "        self.tape = [ \"▷\" ] + [str(a) for a in x ] + [ \"∅\" ]\n",
    "        self.state = \"START\"\n",
    "        self.head = 0 \n",
    "    \n",
    "    def printstate(self, header= True):\n",
    "        tape_ = [self.tape[i] if i != self.head else myred(self.tape[i]) for i in range(len(self.tape))]\n",
    "        if header:\n",
    "            print(mygreen(\"State\".ljust(self.lenstate))+ \" \" +mygreen(\"Tape\"))\n",
    "        print(self.state.ljust(self.lenstate) + \" \"+ \"\".join(tape_))\n",
    "        return None\n",
    "    \n",
    "    def config(self):\n",
    "        n = len(self.states)\n",
    "        k = self.states.index(self.state)\n",
    "        l = len(str(n-1))\n",
    "        tlen = len(self.tape)\n",
    "        for i in range(tlen-1,0,-1):\n",
    "            if self.tape[i] != \"∅\":\n",
    "                break\n",
    "        tlen = i+1\n",
    "        alph = r\"\\{\" + \", \".join(self.alphabet) +r\"\\}\"\n",
    "        states = f\"([{n}]\" + r\" \\cup \\{ \\cdot \\})\"\n",
    "        display(Math(r\"\\text{configuration} \\in \\left(\" + alph + r\"  \\times \" + states +r\"\\right)^*\" ))\n",
    "        tape_ = [self.tape[i].ljust(l) if i != self.head else myred(self.tape[i].ljust(l)) for i in range(tlen)]\n",
    "        states_ = [\"⋅\".ljust(l) if i != self.head else myred(str(k).ljust(l))for i in range(tlen)]\n",
    "        print(\"\".join(tape_))\n",
    "        print(\"\".join(states_))\n",
    "        print(f\"\\nState {k} =  {self.state}\")\n",
    "        \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",
    "            \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 not maxsteps:\n",
    "            maxsteps = self.MAXSTEPS\n",
    "        t = 0\n",
    "        noprinting = 0\n",
    "        quit_cmd = False\n",
    "        if iterate:\n",
    "            print(\"q(uit), n(ext),p(rev),c(lear),r(un),s(kip) XX:\")\n",
    "        try:\n",
    "            while True:\n",
    "                if noprinting>0:\n",
    "                    noprinting -= 1\n",
    "                else:\n",
    "                    if iterate: \n",
    "                        ... # self.reprint()\n",
    "                    else:\n",
    "                        time.sleep(0.5)\n",
    "                    self.printstate(header = t==0)\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",
    "                        noprinting = int(cmd[1:].strip())\n",
    "                        print(\"...\")\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(header = iterate)\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": "code",
   "execution_count": 17,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[32mState    \u001b[0m \u001b[32mTape\u001b[0m\n",
      "START     \u001b[91m▷\u001b[0m10011∅\n",
      "EVEN      ▷\u001b[91m1\u001b[0m0011∅\n",
      "ODD       ▷1\u001b[91m0\u001b[0m011∅\n",
      "ODD       ▷10\u001b[91m0\u001b[0m11∅\n",
      "ODD       ▷100\u001b[91m1\u001b[0m1∅\n",
      "EVEN      ▷1001\u001b[91m1\u001b[0m∅\n",
      "ODD       ▷10011\u001b[91m∅\u001b[0m\n",
      "OUTPUT1   ▷1001\u001b[91m1\u001b[0m∅\n",
      "OUTPUT1   ▷100\u001b[91m1\u001b[0m∅∅\n",
      "OUTPUT1   ▷10\u001b[91m0\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": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MXOR = TuringMachine(xortm)\n",
    "MXOR.input([1,0,0,1,1]) \n",
    "MXOR.run()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[32mState    \u001b[0m \u001b[32mTape\u001b[0m\n",
      "START     \u001b[91m▷\u001b[0m1001∅\n",
      "EVEN      ▷\u001b[91m1\u001b[0m001∅\n",
      "ODD       ▷1\u001b[91m0\u001b[0m01∅\n",
      "ODD       ▷10\u001b[91m0\u001b[0m1∅\n",
      "ODD       ▷100\u001b[91m1\u001b[0m∅\n",
      "EVEN      ▷1001\u001b[91m∅\u001b[0m\n",
      "OUTPUT0   ▷100\u001b[91m1\u001b[0m∅\n",
      "OUTPUT0   ▷10\u001b[91m0\u001b[0m∅∅\n",
      "OUTPUT0   ▷1\u001b[91m0\u001b[0m∅∅∅\n",
      "OUTPUT0   ▷\u001b[91m1\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": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MXOR.input([1,0,0,1]) \n",
    "MXOR.run()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>\n",
       ".table-bordered {\n",
       "    border-collapse: collapse;\n",
       "}\n",
       ".table-bordered th, .table-bordered td {\n",
       "    border: 1px solid black;\n",
       "    padding: 5px;\n",
       "    text-align: left !important;\n",
       "}\n",
       "\n",
       ".table-bordered th:nth-child(2), .table-bordered td:nth-child(2) {\n",
       "    border-right: 3px solid black;\n",
       "}\n",
       ".table-bordered th {\n",
       "    border-bottom: 3px solid black !important;\n",
       "}\n",
       "</style>\n",
       "<table class=\"table-bordered\">\n",
       "<thead>\n",
       "<tr>\n",
       "<th>Curr State</th>\n",
       "<th>Curr Sym</th>\n",
       "<th>New State</th>\n",
       "<th>New Sym</th>\n",
       "<th>Move</th>\n",
       "</tr>\n",
       "</thead><tbody>\n",
       "<tr>\n",
       "<td>0 (START)</td>\n",
       "<td>▷</td>\n",
       "<td>EVEN</td>\n",
       "<td>▷</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>∅</td>\n",
       "<td>EVEN</td>\n",
       "<td>∅</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>0</td>\n",
       "<td>EVEN</td>\n",
       "<td>0</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>1</td>\n",
       "<td>EVEN</td>\n",
       "<td>1</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>1 (EVEN)</td>\n",
       "<td>▷</td>\n",
       "<td>EVEN</td>\n",
       "<td>▷</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>∅</td>\n",
       "<td>OUTPUT0</td>\n",
       "<td>∅</td>\n",
       "<td>L</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>0</td>\n",
       "<td>EVEN</td>\n",
       "<td>0</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>1</td>\n",
       "<td>ODD</td>\n",
       "<td>1</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>2 (ODD)</td>\n",
       "<td>▷</td>\n",
       "<td>ODD</td>\n",
       "<td>▷</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>∅</td>\n",
       "<td>OUTPUT1</td>\n",
       "<td>∅</td>\n",
       "<td>L</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>0</td>\n",
       "<td>ODD</td>\n",
       "<td>0</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>1</td>\n",
       "<td>EVEN</td>\n",
       "<td>1</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>3 (OUTPUT1)</td>\n",
       "<td>▷</td>\n",
       "<td>1ANDSTOP</td>\n",
       "<td>▷</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>∅</td>\n",
       "<td>OUTPUT1</td>\n",
       "<td>∅</td>\n",
       "<td>L</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>0</td>\n",
       "<td>OUTPUT1</td>\n",
       "<td>∅</td>\n",
       "<td>L</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>1</td>\n",
       "<td>OUTPUT1</td>\n",
       "<td>∅</td>\n",
       "<td>L</td>\n",
       "</tr><tr>\n",
       "<td>4 (OUTPUT0)</td>\n",
       "<td>▷</td>\n",
       "<td>0ANDSTOP</td>\n",
       "<td>▷</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>∅</td>\n",
       "<td>OUTPUT0</td>\n",
       "<td>∅</td>\n",
       "<td>L</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>0</td>\n",
       "<td>OUTPUT0</td>\n",
       "<td>∅</td>\n",
       "<td>L</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>1</td>\n",
       "<td>OUTPUT0</td>\n",
       "<td>∅</td>\n",
       "<td>L</td>\n",
       "</tr><tr>\n",
       "<td>5 (1ANDSTOP)</td>\n",
       "<td>▷</td>\n",
       "<td>1ANDSTOP</td>\n",
       "<td>1</td>\n",
       "<td>H</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>∅</td>\n",
       "<td>1ANDSTOP</td>\n",
       "<td>1</td>\n",
       "<td>H</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>0</td>\n",
       "<td>1ANDSTOP</td>\n",
       "<td>1</td>\n",
       "<td>H</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>1</td>\n",
       "<td>1ANDSTOP</td>\n",
       "<td>1</td>\n",
       "<td>H</td>\n",
       "</tr><tr>\n",
       "<td>6 (0ANDSTOP)</td>\n",
       "<td>▷</td>\n",
       "<td>0ANDSTOP</td>\n",
       "<td>0</td>\n",
       "<td>H</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>∅</td>\n",
       "<td>0ANDSTOP</td>\n",
       "<td>0</td>\n",
       "<td>H</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>0</td>\n",
       "<td>0ANDSTOP</td>\n",
       "<td>0</td>\n",
       "<td>H</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>1</td>\n",
       "<td>0ANDSTOP</td>\n",
       "<td>0</td>\n",
       "<td>H</td>\n",
       "</tr>\n",
       "</tbody><table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "MXOR.printtable(True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "q(uit), n(ext),p(rev),c(lear),r(un),s(kip) XX:\n",
      "\u001b[32mState    \u001b[0m \u001b[32mTape\u001b[0m\n",
      "START     \u001b[91m▷\u001b[0m101∅\n",
      "\n",
      "EVEN      ▷\u001b[91m1\u001b[0m01∅\n",
      "\n",
      "ODD       ▷1\u001b[91m0\u001b[0m1∅\n",
      "\n",
      "ODD       ▷10\u001b[91m1\u001b[0m∅\n",
      "\n",
      "EVEN      ▷101\u001b[91m∅\u001b[0m\n",
      "q\n",
      "User quit\n"
     ]
    }
   ],
   "source": [
    "MXOR.input([1,0,1])\n",
    "MXOR.run(True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Confugation of a Turing machine\n",
    "MXOR.input([1,0,1])\n",
    "MXOR.next()\n",
    "MXOR.next()\n",
    "MXOR.next()\n",
    "MXOR.config()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "### Factor out boilerplate\n",
    "\n",
    "(Can skip)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "tags": []
   },
   "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": 26,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "tags": []
   },
   "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": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "MXOR = TuringMachine(xortm)\n",
    "MXOR.printtable(False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "MXOR.input(\"1011\")\n",
    "MXOR.printstate()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "MXOR.run(True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Palindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "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": 27,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "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 == \"∅\": 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",
    "            state = \"OUTPUT0\" if state[4] != state[9] else \"ERASE\"\n",
    "            move  = \"L\"\n",
    "        else: state, move = state[:-1]+sym, \"R\"\n",
    "    elif state == \"ERASE\":\n",
    "        if sym == \"∅\": state,move = \"LEFTMOST\",\"R\"\n",
    "        else: state,sym,move = \"SCANLEFT\", \"∅\", \"L\"\n",
    "    elif state == \"SCANLEFT\":\n",
    "        if sym == \"∅\": state,move = \"LEFTMOST\",\"R\"\n",
    "        else: move = \"L\"\n",
    "    else:\n",
    "        state,sym,move = boilerplate(state,sym)\n",
    "    return state,sym,move"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>\n",
       ".table-bordered {\n",
       "    border-collapse: collapse;\n",
       "}\n",
       ".table-bordered th, .table-bordered td {\n",
       "    border: 1px solid black;\n",
       "    padding: 5px;\n",
       "    text-align: left !important;\n",
       "}\n",
       "\n",
       ".table-bordered th:nth-child(2), .table-bordered td:nth-child(2) {\n",
       "    border-right: 3px solid black;\n",
       "}\n",
       ".table-bordered th {\n",
       "    border-bottom: 3px solid black !important;\n",
       "}\n",
       "</style>\n",
       "<table class=\"table-bordered\">\n",
       "<thead>\n",
       "<tr>\n",
       "<th>Curr State</th>\n",
       "<th>Curr Sym</th>\n",
       "<th>New State</th>\n",
       "<th>New Sym</th>\n",
       "<th>Move</th>\n",
       "</tr>\n",
       "</thead><tbody>\n",
       "<tr>\n",
       "<td>0 (START)</td>\n",
       "<td>▷</td>\n",
       "<td>LEFTMOST</td>\n",
       "<td>▷</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>∅</td>\n",
       "<td>START</td>\n",
       "<td>∅</td>\n",
       "<td>H</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>0</td>\n",
       "<td>START</td>\n",
       "<td>0</td>\n",
       "<td>H</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>1</td>\n",
       "<td>START</td>\n",
       "<td>1</td>\n",
       "<td>H</td>\n",
       "</tr><tr>\n",
       "<td>1 (SCANLEFT)</td>\n",
       "<td>▷</td>\n",
       "<td>LEFTMOST</td>\n",
       "<td>▷</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>∅</td>\n",
       "<td>LEFTMOST</td>\n",
       "<td>∅</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>0</td>\n",
       "<td>SCANLEFT</td>\n",
       "<td>0</td>\n",
       "<td>L</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>1</td>\n",
       "<td>SCANLEFT</td>\n",
       "<td>1</td>\n",
       "<td>L</td>\n",
       "</tr><tr>\n",
       "<td>2 (LEFTMOST)</td>\n",
       "<td>▷</td>\n",
       "<td>LOOK1_SAW1</td>\n",
       "<td>∅</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>∅</td>\n",
       "<td>OUTPUT1</td>\n",
       "<td>∅</td>\n",
       "<td>S</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>0</td>\n",
       "<td>LOOK0_SAW0</td>\n",
       "<td>∅</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>1</td>\n",
       "<td>LOOK1_SAW1</td>\n",
       "<td>∅</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>3 (LOOK0_SAW0)</td>\n",
       "<td>▷</td>\n",
       "<td>LOOK0_SAW▷</td>\n",
       "<td>▷</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>∅</td>\n",
       "<td>ERASE</td>\n",
       "<td>∅</td>\n",
       "<td>L</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>0</td>\n",
       "<td>LOOK0_SAW0</td>\n",
       "<td>0</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>1</td>\n",
       "<td>LOOK0_SAW1</td>\n",
       "<td>1</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>4 (LOOK1_SAW1)</td>\n",
       "<td>▷</td>\n",
       "<td>LOOK1_SAW▷</td>\n",
       "<td>▷</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>∅</td>\n",
       "<td>ERASE</td>\n",
       "<td>∅</td>\n",
       "<td>L</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>0</td>\n",
       "<td>LOOK1_SAW0</td>\n",
       "<td>0</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>1</td>\n",
       "<td>LOOK1_SAW1</td>\n",
       "<td>1</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>5 (LOOK0_SAW1)</td>\n",
       "<td>▷</td>\n",
       "<td>LOOK0_SAW▷</td>\n",
       "<td>▷</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>∅</td>\n",
       "<td>OUTPUT0</td>\n",
       "<td>∅</td>\n",
       "<td>L</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>0</td>\n",
       "<td>LOOK0_SAW0</td>\n",
       "<td>0</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>1</td>\n",
       "<td>LOOK0_SAW1</td>\n",
       "<td>1</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>6 (LOOK1_SAW0)</td>\n",
       "<td>▷</td>\n",
       "<td>LOOK1_SAW▷</td>\n",
       "<td>▷</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>∅</td>\n",
       "<td>OUTPUT0</td>\n",
       "<td>∅</td>\n",
       "<td>L</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>0</td>\n",
       "<td>LOOK1_SAW0</td>\n",
       "<td>0</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>1</td>\n",
       "<td>LOOK1_SAW1</td>\n",
       "<td>1</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>7 (ERASE)</td>\n",
       "<td>▷</td>\n",
       "<td>SCANLEFT</td>\n",
       "<td>∅</td>\n",
       "<td>L</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>∅</td>\n",
       "<td>LEFTMOST</td>\n",
       "<td>∅</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>0</td>\n",
       "<td>SCANLEFT</td>\n",
       "<td>∅</td>\n",
       "<td>L</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>1</td>\n",
       "<td>SCANLEFT</td>\n",
       "<td>∅</td>\n",
       "<td>L</td>\n",
       "</tr><tr>\n",
       "<td>_boilerplate_</td>\n",
       "<td>...</td>\n",
       "<td>...</td>\n",
       "<td>...</td>\n",
       "<td>...</td>\n",
       "</tr>\n",
       "</tbody><table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": []
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "PalM = TuringMachine(palindrome)\n",
    "PalM"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[32mState       \u001b[0m \u001b[32mTape\u001b[0m\n",
      "START        \u001b[91m▷\u001b[0m110∅\n",
      "LEFTMOST     ▷\u001b[91m1\u001b[0m10∅\n",
      "LOOK1_SAW1   ▷∅\u001b[91m1\u001b[0m0∅\n",
      "LOOK1_SAW1   ▷∅1\u001b[91m0\u001b[0m∅\n",
      "LOOK1_SAW0   ▷∅10\u001b[91m∅\u001b[0m\n",
      "OUTPUT0      ▷∅1\u001b[91m0\u001b[0m∅\n",
      "OUTPUT0      ▷∅\u001b[91m1\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": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "PalM.input(\"110\")\n",
    "PalM.run()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Turing Machines don't have to halt!!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>\n",
       ".table-bordered {\n",
       "    border-collapse: collapse;\n",
       "}\n",
       ".table-bordered th, .table-bordered td {\n",
       "    border: 1px solid black;\n",
       "    padding: 5px;\n",
       "    text-align: left !important;\n",
       "}\n",
       "\n",
       ".table-bordered th:nth-child(2), .table-bordered td:nth-child(2) {\n",
       "    border-right: 3px solid black;\n",
       "}\n",
       ".table-bordered th {\n",
       "    border-bottom: 3px solid black !important;\n",
       "}\n",
       "</style>\n",
       "<table class=\"table-bordered\">\n",
       "<thead>\n",
       "<tr>\n",
       "<th>Curr State</th>\n",
       "<th>Curr Sym</th>\n",
       "<th>New State</th>\n",
       "<th>New Sym</th>\n",
       "<th>Move</th>\n",
       "</tr>\n",
       "</thead><tbody>\n",
       "<tr>\n",
       "<td>0 (START)</td>\n",
       "<td>▷</td>\n",
       "<td>START</td>\n",
       "<td>▷</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>∅</td>\n",
       "<td>START</td>\n",
       "<td>∅</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>0</td>\n",
       "<td>START</td>\n",
       "<td>0</td>\n",
       "<td>R</td>\n",
       "</tr><tr>\n",
       "<td>--</td>\n",
       "<td>1</td>\n",
       "<td>START</td>\n",
       "<td>1</td>\n",
       "<td>R</td>\n",
       "</tr>\n",
       "</tbody><table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": []
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def nonhalting(state,sym):\n",
    "    return state,sym,\"R\"\n",
    "\n",
    "NH = TuringMachine(nonhalting)\n",
    "NH"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[32mState  \u001b[0m \u001b[32mTape\u001b[0m\n",
      "START   \u001b[91m▷\u001b[0m00111011∅\n"
     ]
    }
   ],
   "source": [
    "NH.input(\"00111011\")\n",
    "NH.printstate()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "q(uit), n(ext),p(rev),c(lear),r(un),s(kip) XX:\n",
      "\u001b[32mState  \u001b[0m \u001b[32mTape\u001b[0m\n",
      "START   \u001b[91m▷\u001b[0m00111011∅\n",
      "\n",
      "START   ▷\u001b[91m0\u001b[0m0111011∅\n",
      "\n",
      "START   ▷0\u001b[91m0\u001b[0m111011∅\n",
      "\n",
      "START   ▷00\u001b[91m1\u001b[0m11011∅\n",
      "\n",
      "START   ▷001\u001b[91m1\u001b[0m1011∅\n",
      "\n",
      "START   ▷0011\u001b[91m1\u001b[0m011∅\n",
      "\n",
      "START   ▷00111\u001b[91m0\u001b[0m11∅\n",
      "\n",
      "START   ▷001110\u001b[91m1\u001b[0m1∅\n",
      "\n",
      "START   ▷0011101\u001b[91m1\u001b[0m∅\n",
      "\n",
      "START   ▷00111011\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "\n",
      "START   ▷00111011∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅∅\u001b[91m∅\u001b[0m\n",
      "q\n",
      "User quit\n"
     ]
    }
   ],
   "source": [
    "NH.run(True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "__Def:__ If $M$ is Turing Machine and $x\\in \\{0,1\\}^*$ then $M(x)$ denotes the contents of tape of $M$ from second position  until  first empty spot. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "If $M(x)$ doesn't halt we denote $M(x) = \\bot$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "__Super important def:__ A TM $M$ _computes_ $F:\\{0,1\\}^* \\rightarrow \\{0,1\\}^*$  if for every $x\\in \\{0,1\\}^*$, $M(x) = F(x)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "$F$ is _computable_ if there is a TM that computes it"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Back to Powerpoint"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "tcs",
   "language": "python",
   "name": "tcs"
  },
  "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.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}