OLD_NANDpp_overview.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## NAND++ overview\n",
    "\n",
    "This notebook gives an overview of the NAND++ language. We use Python code to illustrate some concepts, but you don't need to know Python at all to follow. In fact, in the first read I recommend you skip all the code cells.\n",
    "\n",
    "This notebook should be useful for you even if you view it statically, but might be even better if you play with on jupyter notebook."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is NAND++?\n",
    "\n",
    "The right way to think about NAND++ is that it has the following two features compared to NAND:\n",
    "\n",
    "* All variables except the special index variable `i` are  _arrays_. Each variable in a line of code of NAND++ is either indexed by a fixed numerical index (as in `foo_17`) or by the special index `i`, (as in `bar_i`). If an index is missing (as in `blah`) we treat at as 0 (and so `blah` and `blah_0` refer to the same variable).\n",
    "\n",
    "* NAND is  a _straightline programming language_ that has no loops, and so if the program has $s$ lines then on every input it runs for exactly $s$ steps. NAND++ has the special `loop` variable (which is the same as `loop_0`, by our convention above), such that when an iteration ends, if `loop` equals $1$, then the program starts from the beginning. An _iteration_ of an $s$ lines NAND++ program takes $s$ steps, and the number of iterations such a programs takes depends on the input that it gets. \n",
    "\n",
    "* The special index variable `i` either increases or decreases by one at the end of every iteration. It follows the following schedule $0,1,0,1,2,1,0,1,2,3,2,1,0,1,2,3,2,2,1,0,\\ldots$. There is also a formula for this schedule. The only thing you have to remember about it is that it exists, and is not that complicated. In fact, we can write it in a couple of lines of math or  Python (as shown in the next cell):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "# Returns the value of the index variable i in  iteration number k\n",
    "def index(k):\n",
    "    r = math.floor(math.sqrt(k+1/4)-1/2)\n",
    "    return (k-r*(r+1) if k <= (r+1)*(r+1) else (r+1)*(r+2)-k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 0, 1, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 2, 3, 4, 3, 2, 1]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[index(k) for k in range(20)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code of a NAND++ program looks almost exactly like the code of a NAND program except for the presence of the index variable `i`. The main difference is that when we run a NAND++ program we do two things:\n",
    "\n",
    "1. In iteration $k$ we replace all references to $i$ with references to $index(k)$\n",
    "\n",
    "2. When we get to the end, if `loop` is equal to 0 then we go back to the beginning.\n",
    "\n",
    "One more minor difference is that because the input in a NAND++ program does not have a fixed length, in addition to the variables `x_0`, `x_1`, ... that give us the bits of the input, we also have variables `validx_0`,`validx_1`, ... such that `validx_`$j$ evaluates to $1$ if and only if $j$ is smaller than the length of the input. (Otherwise, the program would not be able to determine the length of the input.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above means that if we have an interpeter for NAND, we can write an interpreter for NAND++ by simply invoking it many times, using the search and replace as above. Here is some Python code that does that:\n",
    "\n",
    "The function `NANDinterpeter` gets a NAND program and a table of the values of its variables, and runs the NAND program to update this table.\n",
    "\n",
    "The function `NANDPPinterpeter` gets a NAND++ program P and an input x as input. It initializes a table corresponding to the input, and then continusly feeds the program P to the NAND interpeter (replacing in iteration $k$ the value of `i`  with $index(k)$)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Gets as input a NAND program and a table of values of variables. \n",
    "# Runs an iteration of the program, updating the values of the variables as it proceeds\n",
    "def NANDinterpeter(prog,variables):\n",
    "    for line in prog.split('\\n'):\n",
    "        (var1,_,var2,__,var3) = line.split()\n",
    "        variables[var1] = 1-variables.get(var2,0)*variables.get(var3,0)\n",
    "        \n",
    "# p.s. This code is a bit brittle: sensitive to spaces, comments, and other issues."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Gets as input a NAND++ program and an input (as an array of 0/1 values) and returns the evaluation of the program on this input\n",
    "# Works by repeatedly calling NAND\n",
    "def NANDPPinterpreter(prog,x):\n",
    "    n = len(x)\n",
    "    variables = {}\n",
    "    for i in range(n):\n",
    "        variables['x_'+str(i)]=x[i]\n",
    "        variables['validx_'+str(i)]=1\n",
    "    k=0\n",
    "    while True:\n",
    "        NANDprog = prog.replace( '_i','_'+str(index(k)))\n",
    "        NANDinterpeter(NANDprog,variables)\n",
    "        if variables.get('loop',0)==0: break\n",
    "        k += 1\n",
    "    \n",
    "    return variables.get('y_0',0) # assume one bit output"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try this out on the parity program from the lecture notes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "parity = r'''tmpa  := seen_i NAND seen_i\n",
    "tmpb  := x_i NAND tmpa\n",
    "val   :=  tmpb NAND tmpb\n",
    "ns   := s   NAND s\n",
    "y_0  := ns  NAND ns\n",
    "u    := val NAND s\n",
    "v    := s   NAND u\n",
    "w    := val NAND u\n",
    "s    := v   NAND w\n",
    "seen_i := zero NAND zero  \n",
    "stop := validx_i NAND validx_i\n",
    "loop := stop     NAND stop'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "NANDPPinterpreter(parity,[0,1,1,0,0,1,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "NANDPPinterpreter(parity,[0,1,1,0,0,1,0,0,1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's all there is to NAND++. It is an extremely simple programming language. The surprising thing is that it is equivalent to NAND<< and other more powerful languages. That is, ultimately we can implement NAND<< (or even Python) as \"syntactic sugar\" on top of NAND++. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Translating  NAND<< to NAND++\n",
    "\n",
    "NAND<< (and other such more powerful languages) are inherently more complex to describe. A fairly complete description of NAND<< is in Appendix A, but to write things in full formality and detail would require much more space. The specification of C,C++ or Python can run to hunderds of pages. The fact that the specification is long means that a full formal proof of the equivalence of NAND++ and NAND<< would be very long and detailed, and not that insightful. (This is not something specific for NAND++ and NAND<<, the full formal proof that Turing machines are equivalent to RAM machines, for example would be just as long.)\n",
    "\n",
    "I do not expect you to know all this proof by heart, but to understand the _key steps_ in it, which are illustrated in the lecture notes. In particular, the most significant step is the transformation, using the \"breadcrumbs\" technique, of a NAND++ that uses the `i++` and `i--` syntactic sugar, to the a program that does not use it. \n",
    "\n",
    "The main component  of that technique is the ability of a NAND++ program to know when an index is increasing or decreasing: that is create an `indexincreasing` variable that is equal to $1$ when the index will be _incremented_ in the next stepand equal to $0$ when the index will be _decremented_ in the next step.\n",
    "\n",
    "Usng this, to simulate the `i--` operation we look at `indexincreasing`: if it is equal to $0$ then we do nothing, if it is equal to $1$ then we mark the current location of `i` using a special array `marker_i`, and do nothing  until we reach the same location with the value of `indexincreasing` equal to $1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Simulating `indexincreasing` \n",
    "\n",
    "I will not include here the Python code to implement all of the above sugar, but here is a Python function that modifies a NAND++ program $P$ to a NAND++ program $P'$ that has the `indexincreasing` variable.\n",
    "\n",
    "At one step we will want to assign to `indexincreasing` the value `F(atstart_i,breadcrumbs_i,indexincreasing)` where $F:\\{0,1\\}^3 \\rightarrow \\{0,1\\}$ is defined as $F(1,\\cdot,\\cdot)=1$, $F(0,0,\\cdot)=0$ and $F(0,1,a)=a$. That is, if we are at the beginning then `indexincreasing` should be equal to $1$, if we reach a point we haven't seen before, then `indexincreasing` should be equal to $0$, and otherwise it should stay the same.\n",
    "\n",
    "This is just a finite function and so we can construct a NAND code for it (which you will see in the Python code below)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def idxincreasing(prog):\n",
    "    prog = \"atstart_0 := zero NAND zero\\n\"+prog # ensure atstart is array (1,0,0,0,....)\n",
    "    prog += r'''\n",
    "tempidx := breadcrumbs_i NAND indexincreasing\n",
    "notstart := atstart_i NAND atstart_i\n",
    "indexincreasing := notstart NAND tempidx\n",
    "breadcrumbs_i := zero NAND zero'''\n",
    "    return prog    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we run it for the parity program, we get the following variant:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "atstart_0 := zero NAND zero\n",
      "tmpa  := seen_i NAND seen_i\n",
      "tmpb  := x_i NAND tmpa\n",
      "val   :=  tmpb NAND tmpb\n",
      "ns   := s   NAND s\n",
      "y_0  := ns  NAND ns\n",
      "u    := val NAND s\n",
      "v    := s   NAND u\n",
      "w    := val NAND u\n",
      "s    := v   NAND w\n",
      "seen_i := zero NAND zero  \n",
      "stop := validx_i NAND validx_i\n",
      "loop := stop     NAND stop\n",
      "tempidx := breadcrumbs_i NAND indexincreasing\n",
      "notstart := atstart_i NAND atstart_i\n",
      "indexincreasing := notstart NAND tempidx\n",
      "breadcrumbs_i := zero NAND zero\n"
     ]
    }
   ],
   "source": [
    "parityidx = idxincreasing(parity)\n",
    "print(parityidx)\n",
    "                          "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To see if it works, let's rerun this with a version of our interpeter that prints the `indexincreasing` variable: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Gets as input a NAND++ program and an input (as an array of 0/1 values) and returns the evaluation of the program on this input\n",
    "# Works by repeatedly calling NAND\n",
    "def NANDPPinterpreter(prog,x,track = []):\n",
    "    n = len(x)\n",
    "    variables = {}\n",
    "    for i in range(n):\n",
    "        variables['x_'+str(i)]=x[i]\n",
    "        variables['validx_'+str(i)]=1\n",
    "    k=0\n",
    "    while True:\n",
    "        NANDprog = prog.replace( '_i','_'+str(index(k)))\n",
    "        NANDinterpeter(NANDprog,variables)\n",
    "        if variables.get('loop',0)==0: break\n",
    "        for v in track: print(v + \" = \"+ str(variables.get(v,0)))\n",
    "        k += 1\n",
    "    \n",
    "    return variables.get('y_0',0) # assume one bit output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "indexincreasing = 1\n",
      "indexincreasing = 0\n",
      "indexincreasing = 1\n",
      "indexincreasing = 1\n",
      "indexincreasing = 0\n",
      "indexincreasing = 0\n",
      "indexincreasing = 1\n",
      "indexincreasing = 1\n",
      "indexincreasing = 1\n",
      "indexincreasing = 0\n",
      "indexincreasing = 0\n",
      "indexincreasing = 0\n",
      "indexincreasing = 1\n",
      "indexincreasing = 1\n",
      "indexincreasing = 1\n",
      "indexincreasing = 1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "NANDPPinterpreter(parityidx,[0,1,1,0],[\"indexincreasing\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can see that we have a sequence of increasing once, then decreasing once, then increasing twice, then decreasing twice, and so on and so forth"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Configurations\n",
    "\n",
    "The notion of _configurations_ is just to encode the entire contents of the state of a NAND++ program. The exact details of a configurations are not as important as are the following high level points:\n",
    "\n",
    "* The state of a NAND++ program has components that are fixed independently of the input and the number of steps: the current line, the number of lines, and the values of all array locations that are indexed by an absolute numerical index such as `foo_17`. It also has components that can grow as the number of steps grow: the value of the index variable `i`, and the contents of the arrays in all the locations that `i` has been to so far. \n",
    "\n",
    "* As we run more steps, we access more memory locations, and so the size of the configuration grows.\n",
    "\n",
    "* We use blocks to encode the configuration for convience. The size of each block is a constant (that depends on the number of lines in the program), but the number of blocks can grow. Block number $j$ contains the contents of all variables that are of the form `foo_`$j$. If $j$ is equal to the current value of the index variable `i` then this block is  the _active_ block, and the configuration contains a bit that marks this condition.\n",
    "\n",
    "* For every NAND++ program $P$, the $NEXT_P$ function computes the next configuration of the program $P$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For every NAND++ program $P$, the $NEXT_P$ function maps one configuration to the next one. It can be implemented by fairly simple \"search and replace\". This is done in the Python code below, though again I would skip it in a first read. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "# compute the next-step configuration\n",
    "# Inputs:\n",
    "# P: NAND++ program in list of 6-tuples representation  (assuming it has an \"indexincreasing\" variable)\n",
    "# conf: encoding of configuration as a string using the alphabet \"B\",\"E\",\"0\",\"1\".\n",
    "def next_step(P,conf):\n",
    "    s = len(P) # numer of lines\n",
    "    t = max([max(tup[0],tup[2],tup[4]) for tup in P])+1 # number of variables\n",
    "    line_enc_length = math.ceil(math.log(s+1,2)) # num of bits to encode a line\n",
    "    block_enc_length = t+3+line_enc_length # num of bits to encode a block (without bookends of \"E\",\"B\")\n",
    "    LOOP = 3\n",
    "    INDEXINCREASING = 5\n",
    "    ACTIVEIDX = block_enc_length -line_enc_length-1 # position of active flag\n",
    "    FINALIDX =  block_enc_length  -line_enc_length-2 # position of final flag\n",
    "    \n",
    "    def getval(var,idx):\n",
    "        if idx<s: return int(blocks[idx][var])\n",
    "        return int(active[var])\n",
    "    \n",
    "    def setval(var,idx,v):\n",
    "        nonlocal blocks, i\n",
    "        if idx<s: blocks[idx][var]=str(v)\n",
    "        blocks[i][var]=str(v)\n",
    "    \n",
    "    blocks = [list(b[1:]) for b in conf.split(\"E\")[:-1]] # list of blocks w/o initial \"B\" and final \"E\"\n",
    "    \n",
    "    i = [j for j in range(len(blocks))  if blocks[j][ACTIVEIDX]==\"1\" ][0]\n",
    "    active = blocks[i]\n",
    "    \n",
    "    p = int(\"\".join(active[-line_enc_length:]),2) # current line to be executed\n",
    "    \n",
    "    if p==s: return conf # halting configuration\n",
    "    \n",
    "    (a,j,b,k,c,l) = P[p] #  6-tuple corresponding to current line#  6-tuple corresponding to current line\n",
    "    setval(a,j,1-getval(b,k)*getval(c,l))\n",
    "    \n",
    "    new_p = p+1\n",
    "    new_i = i\n",
    "    if p==s-1: # last line\n",
    "        new_p = (s if getval(LOOP,0)==0 else 0)\n",
    "        new_i = (i+1 if getval(INDEXINCREASING,0) else i-1)\n",
    "        if new_i==len(blocks): # need to add another block and make it final\n",
    "            blocks[len(blocks)-1][FINALIDX]=\"0\"\n",
    "            new_final = [\"0\"]*block_enc_length\n",
    "            new_final[FINALIDX]=\"1\"\n",
    "            blocks.append(new_final)\n",
    "        \n",
    "        blocks[i][ACTIVEIDX]=\"0\" # turn off \"active\" flag in old active block\n",
    "        blocks[i][ACTIVEIDX+1:ACTIVEIDX+1+line_enc_length]=[\"0\"]*line_enc_length # zero out line counter in old active block\n",
    "        blocks[new_i][ACTIVEIDX]=\"1\" # turn on \"active\" flag in new active block\n",
    "    new_p_s = bin(new_p)[2:]\n",
    "    new_p_s = \"0\"*(line_enc_length-len(new_p_s))+new_p_s\n",
    "    blocks[new_i][ACTIVEIDX+1:ACTIVEIDX+1+line_enc_length] = list(new_p_s) # add binary representation of next line in new active block\n",
    "    \n",
    "    return \"\".join([\"B\"+\"\".join(block)+\"E\" for block in blocks]) # return new configuration\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The _initial configuration_ encodes the input. The code below (which again you should skip in a first read)  returns a string encoding this initial configuration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# return initial configuration of P with input x\n",
    "def initial_conf(P,x):\n",
    "    s = len(P) # numer of lines\n",
    "    t = max([max(tup[0],tup[2],tup[4]) for tup in P])+1 # number of variables\n",
    "    \n",
    "    line_enc_length = math.ceil(math.log(s+1,2)) # num of bits to encode a line\n",
    "    block_enc_length = t+3+line_enc_length # num of bits to encode a block (without bookends of \"E\",\"B\")\n",
    "    \n",
    "     # largest numerical index:\n",
    "    largest_idx =  max([max((0 if tup[1]==s else tup[1]),(0 if tup[3]==s else tup[3]),(0 if tup[5]==s else tup[5])) for tup in P]) \n",
    "    \n",
    "    ACTIVEIDX = block_enc_length -line_enc_length-1 # position of active flag\n",
    "    FINALIDX =  block_enc_length  -line_enc_length-2 # position of final flag\n",
    "    INITIALIDX =  block_enc_length  -line_enc_length-3 # position of initial flag\n",
    "\n",
    "    num_blocks = max(len(x),largest_idx+1)\n",
    "    blocks = [[\"B\"]+[\"0\"]*block_enc_length+[\"E\"] for i in range(num_blocks)]\n",
    "    blocks[0][1+INITIALIDX]=\"1\"\n",
    "    blocks[0][1+ACTIVEIDX]=\"1\"\n",
    "    blocks[num_blocks-1][FINALIDX]=\"1\"\n",
    "    for i in range(len(x)):\n",
    "        blocks[i][1]=x[i]\n",
    "        blocks[i][3]=\"1\"\n",
    "    return \"\".join([\"\".join(b) for b in blocks])\n",
    "     "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We also add a couple of \"helper functions\" to print nicely the configuration (and check if it's halting by simply checking if the next_step function does nothing on it or not). Once again, please ignore the code in a first read"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "          \n",
    "def is_halting(P,conf):\n",
    "    newconf = next_step(P,conf)\n",
    "    return newconf==conf  \n",
    "\n",
    "\n",
    "def bold(s,justify=0):\n",
    "    return \"\\x1b[1m\"+s.ljust(justify)+\"\\x1b[21m\"\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  \"\\x1b[31m\"+s.ljust(justify)+\"\\x1b[0m\"\n",
    "\n",
    "\n",
    "def green(s,justify=0):\n",
    "    return  \"\\x1b[32m\"+s.ljust(justify)+\"\\x1b[0m\"\n",
    "\n",
    "\n",
    "def blue(s,justify=0):\n",
    "    return  \"\\x1b[34m\"+s.ljust(justify)+\"\\x1b[0m\"\n",
    "\n",
    "\n",
    "def print_conf(P,conf):\n",
    "    s = len(P) # numer of lines\n",
    "    t = max([max(tup[0],tup[2],tup[4]) for tup in P])+1 # number of variables\n",
    "    line_enc_length = math.ceil(math.log(s+1,2)) # num of bits to encode a line\n",
    "    block_enc_length = t+3+line_enc_length # num of bits to encode a block (without bookends of \"E\",\"B\")\n",
    "    LOOP = 3\n",
    "    INDEXINCREASING = 5\n",
    "    ACTIVEIDX = block_enc_length -line_enc_length-2 # position of active flag\n",
    "    FINALIDX =  block_enc_length  -line_enc_length-3 # position of final flag\n",
    "    \n",
    "    blocks = [list(b[1:]) for b in conf.split(\"E\")[:-1]] \n",
    "    printout = \"\".join([red(\"B\")+ \"\".join(b[0:t])+\n",
    "                                blue(\"\".join(b[t:t+3]))+green(\"\".join(b[t+3:t+3+line_enc_length]))+\n",
    "                                red(\"E\") for b in blocks])\n",
    "    print(printout)\n",
    "                       "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function below translates a NAND++ program to the standard 6-tuple representation as given in the lecture notes. In this representation, a line of the form `foo_`$j$ ` := ` `bar_`$k$ ` NAND ` `blah_`$\\ell$ is transformed into the 6-tuple $(a,j,b,k,c,\\ell)$ where $a,b,c$ are the numbers corresponding to the identifiers `foo`, `bar` and `blah`.\n",
    "\n",
    "If one or more of the indices is not an absolute number but rather the special index `i` then the corresponding element in the 6-tuple will be the number of lines $s$. (This cannot create any confusion since we cannot use absolute numerical indices larger than $s-1$ in the program.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Parse NAND++ program as sequence of 6-tuples\n",
    "def parsepp(prog):\n",
    "    s = len(prog.split('\\n'))\n",
    "    varsidx = { \"x\":0, \"y\":1, \"validx\":2, \"loop\": 3, \"halted\":4, \"indexincreasing\":5 }\n",
    "    \n",
    "    def idxsub(var):\n",
    "        varsplit = var.split('_')\n",
    "        varid = varsidx.setdefault(varsplit[0],len(varsidx))\n",
    "        sub = (0 if len(varsplit)<2 else (int(varsplit[1]) if varsplit[1]!='i' else s))\n",
    "        return [varid,sub]\n",
    "    \n",
    "    L = []\n",
    "    \n",
    "    for line in prog.split('\\n'):\n",
    "        (var1,_,var2,__,var3) = line.split()\n",
    "        L.append(idxsub(var1)+idxsub(var2)+idxsub(var3))\n",
    "    \n",
    "    return L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[6, 0, 7, 0, 7, 0], [8, 0, 9, 17, 9, 17], [10, 0, 0, 17, 8, 0], [11, 0, 10, 0, 10, 0], [12, 0, 13, 0, 13, 0], [1, 0, 12, 0, 12, 0], [14, 0, 11, 0, 13, 0], [15, 0, 13, 0, 14, 0], [16, 0, 11, 0, 14, 0], [13, 0, 15, 0, 16, 0], [9, 17, 7, 0, 7, 0], [17, 0, 2, 17, 2, 17], [3, 0, 17, 0, 17, 0], [18, 0, 19, 17, 5, 0], [20, 0, 6, 17, 6, 17], [5, 0, 20, 0, 18, 0], [19, 17, 7, 0, 7, 0]]\n"
     ]
    }
   ],
   "source": [
    "L = parsepp(parityidx)\n",
    "print(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is the initial configuration of the parity program on the input \"1011\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'B10100000000000000000010100000EB00100000000000000000000000000EB10100000000000000000000000000EB10100000000000000000010000000E'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "initial_conf(L,\"1011\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And here is the next configuration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'B10100010000000000000010100001EB00100000000000000000000000000EB10100000000000000000000000000EB10100000000000000000010000000E'"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next_step(L,_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And the one after that"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'B10100010100000000000010100010EB00100000000000000000000000000EB10100000000000000000000000000EB10100000000000000000010000000E'"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next_step(L,_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And so we can also evaluate NAND++ programs by repeatedly applying the next step function as follows:\n",
    "\n",
    "In the code below we use `print_conf` to print the configurations with nice colors marking the components of each block:\n",
    "\n",
    "* The red B and E are the \"begin block\" and \"end block\" markers.\n",
    "\n",
    "* The black string corresponds to the contents of all the variables in that block\n",
    "\n",
    "* The three blue bits correspond to the \"initial\", \"final\", and \"active\" flags\n",
    "\n",
    "* The green bits correspond to the current line that is being executed. Note that they are always equal to 0 for non-active blocks.\n",
    "\n",
    "Note also that the configuration grows with the execution (although in the case of the parity program not by much, since this program halts as soon as it reaches one spot beyond the input length)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Evaluate a NAND++ program (represented as a list of tuples)\n",
    "# By repeatedly applying the \"next step\" function\n",
    "def eval_conf(L,x):\n",
    "    conf = initial_conf(L,x)\n",
    "    while not is_halting(L,conf):\n",
    "        print_conf(L,conf)\n",
    "        conf = next_step(L,conf)\n",
    "    return int(conf[2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[31mB\u001b[0m101000000000000000000\u001b[34m101\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000000000000000000\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101000100000000000000\u001b[34m101\u001b[0m\u001b[32m00001\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000000000000000000\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101000101000000000000\u001b[34m101\u001b[0m\u001b[32m00010\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000000000000000000\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101000101000000000000\u001b[34m101\u001b[0m\u001b[32m00011\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000000000000000000\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101000101001000000000\u001b[34m101\u001b[0m\u001b[32m00100\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000000000000000000\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101000101001100000000\u001b[34m101\u001b[0m\u001b[32m00101\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000000000000000000\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101000101001100000000\u001b[34m101\u001b[0m\u001b[32m00110\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000000000000000000\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101000101001101000000\u001b[34m101\u001b[0m\u001b[32m00111\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000000000000000000\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101000101001101100000\u001b[34m101\u001b[0m\u001b[32m01000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000000000000000000\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101000101001101100000\u001b[34m101\u001b[0m\u001b[32m01001\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000000000000000000\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101000101001111100000\u001b[34m101\u001b[0m\u001b[32m01010\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000000000000000000\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101000101101111100000\u001b[34m101\u001b[0m\u001b[32m01011\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000000000000000000\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101000101101111100000\u001b[34m101\u001b[0m\u001b[32m01100\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000000000000000000\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101100101101111100000\u001b[34m101\u001b[0m\u001b[32m01101\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000000000000000000\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101100101101111100100\u001b[34m101\u001b[0m\u001b[32m01110\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000000000000000000\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101100101101111100100\u001b[34m101\u001b[0m\u001b[32m01111\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000000000000000000\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101101101101111100100\u001b[34m101\u001b[0m\u001b[32m10000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000000000000000000\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101101101101111100110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000000000000000000\u001b[34m001\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101101101101111100110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000100000000000000\u001b[34m001\u001b[0m\u001b[32m00001\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101101101101111100110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000101000000000000\u001b[34m001\u001b[0m\u001b[32m00010\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101101101111111100110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000101010000000000\u001b[34m001\u001b[0m\u001b[32m00011\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101101101110111100110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000101010000000000\u001b[34m001\u001b[0m\u001b[32m00100\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101101101110011100110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m001000101010000000000\u001b[34m001\u001b[0m\u001b[32m00101\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101110011100110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011000101010000000000\u001b[34m001\u001b[0m\u001b[32m00110\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101110011100110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011000101010001000000\u001b[34m001\u001b[0m\u001b[32m00111\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101110011000110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011000101010001000000\u001b[34m001\u001b[0m\u001b[32m01000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101110011010110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011000101010001010000\u001b[34m001\u001b[0m\u001b[32m01001\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101110011010110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011000101010011010000\u001b[34m001\u001b[0m\u001b[32m01010\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101110011010110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011000101110011010000\u001b[34m001\u001b[0m\u001b[32m01011\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101110011010110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011000101110011010000\u001b[34m001\u001b[0m\u001b[32m01100\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101110011010110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011100101110011010000\u001b[34m001\u001b[0m\u001b[32m01101\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101110011010110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011100101110011010100\u001b[34m001\u001b[0m\u001b[32m01110\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101110011010110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011100101110011010100\u001b[34m001\u001b[0m\u001b[32m01111\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101110011010110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010100\u001b[34m001\u001b[0m\u001b[32m10000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101110011010110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000000000000000000\u001b[34m101\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101110011010110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000100000000000000\u001b[34m101\u001b[0m\u001b[32m00001\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101110011010110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000101000000000000\u001b[34m101\u001b[0m\u001b[32m00010\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101100011010110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000101000000000000\u001b[34m101\u001b[0m\u001b[32m00011\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101101011010110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000101001000000000\u001b[34m101\u001b[0m\u001b[32m00100\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101101011010110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m101000101001000000000\u001b[34m101\u001b[0m\u001b[32m00101\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101101011010110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111000101001000000000\u001b[34m101\u001b[0m\u001b[32m00110\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101101010010110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111000101001000000000\u001b[34m101\u001b[0m\u001b[32m00111\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101101010110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111000101001000100000\u001b[34m101\u001b[0m\u001b[32m01000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101101010110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111000101001000110000\u001b[34m101\u001b[0m\u001b[32m01001\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111000101001000110000\u001b[34m101\u001b[0m\u001b[32m01010\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111000101101000110000\u001b[34m101\u001b[0m\u001b[32m01011\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111000101101000110000\u001b[34m101\u001b[0m\u001b[32m01100\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111100101101000110000\u001b[34m101\u001b[0m\u001b[32m01101\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111100101101000110100\u001b[34m101\u001b[0m\u001b[32m01110\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111100101101000110100\u001b[34m101\u001b[0m\u001b[32m01111\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111101101101000110100\u001b[34m101\u001b[0m\u001b[32m10000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m000000000000000000000\u001b[34m011\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m000000100000000000000\u001b[34m011\u001b[0m\u001b[32m00001\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m000000101000000000000\u001b[34m011\u001b[0m\u001b[32m00010\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101111000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m000000101010000000000\u001b[34m011\u001b[0m\u001b[32m00011\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101110000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m000000101010000000000\u001b[34m011\u001b[0m\u001b[32m00100\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m111101101110100110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m000000101010100000000\u001b[34m011\u001b[0m\u001b[32m00101\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101101101110100110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m000000101010100000000\u001b[34m011\u001b[0m\u001b[32m00110\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101101101110101110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m000000101010101000000\u001b[34m011\u001b[0m\u001b[32m00111\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101101101110101110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m000000101010101100000\u001b[34m011\u001b[0m\u001b[32m01000\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101101101110101110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m000000101010101110000\u001b[34m011\u001b[0m\u001b[32m01001\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101101101110101110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m000000101010101110000\u001b[34m011\u001b[0m\u001b[32m01010\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101101101110101110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m000000101110101110000\u001b[34m011\u001b[0m\u001b[32m01011\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101101101110101111110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m000000101110101111000\u001b[34m011\u001b[0m\u001b[32m01100\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101001101110101111110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m000000101110101111000\u001b[34m011\u001b[0m\u001b[32m01101\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101001101110101111110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m000000101110101111100\u001b[34m011\u001b[0m\u001b[32m01110\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101001101110101111110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m000000101110101111100\u001b[34m011\u001b[0m\u001b[32m01111\u001b[0m\u001b[31mE\u001b[0m\n",
      "\u001b[31mB\u001b[0m101001101110101111110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m011101101110011010110\u001b[34m000\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m111101101101000110110\u001b[34m100\u001b[0m\u001b[32m00000\u001b[0m\u001b[31mE\u001b[0m\u001b[31mB\u001b[0m000001101110101111100\u001b[34m011\u001b[0m\u001b[32m10000\u001b[0m\u001b[31mE\u001b[0m\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eval_conf(L,\"101\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And we see that the final output is indeed the parity of the input."
   ]
  }
 ],
 "metadata": {
  "kernel_info": {
   "name": "python3"
  },
  "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.2"
  },
  "nteract": {
   "version": "0.3.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}