{
"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. [](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": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"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'(?=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": [
"State | Sym | New State | New Sym | Move \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": [
""
]
},
"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": [
"State | Sym | New State | New Sym | Move \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": [
""
]
},
"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\u001b[0m in \u001b[0;36m\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\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'(?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\u001b[0m in \u001b[0;36m\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\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
}