{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "# Week 10: 2017/04/03-07\n",
    "\n",
    "## Monday\n",
    "\n",
    "Read Section 5.1, up to but not including \"Reductions via Computation Histories.\" "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Tuesday class\n",
    "\n",
    "Now that we've proven that one language ($A_{\\mathsf{TM}}$) is undecidable, we can use it to prove that other languages are undecidable.\n",
    "\n",
    "### The halting problem\n",
    "\n",
    "The first example is the halting problem. In many textbooks (and the poem \"Scooping the Loop Snooper\"), the halting problem is actually the prototypical undecidable language, but Sipser does things a little differently.\n",
    "\n",
    "The proof is not difficult but it has a weird feel to it. The first thing that you have to remember is that the direction of the reduction is the opposite of what most people intuitively think of first. If you want to show that the halting problem is undecidable, you do _not_ reduce the halting problem to $A_{\\mathsf{TM}}$. You assume that the halting problem _is_ decidable, then show via a reduction from $A_{\\mathsf{TM}}$ to the halting problem that $A_{\\mathsf{TM}}$ would also be decidable, which is a contradiction.\n",
    "\n",
    "Recall that we designed $U$, a universal TM, that _recognizes_ $A_{\\mathsf{TM}}$, but we showed that we cannot design a TM $S$, a \"universal decider,\" that _decides_ $A_{\\mathsf{TM}}$. Practically, the sticking point is that on input $\\langle M, w\\rangle$, if $M$ loops on $w$, we have no way to detect it so that we can reject. Enter $R$, a hypothetical TM that decides the halting problem $\\mathit{HALT}_{\\mathsf{TM}}$. If we had such a machine, then designing $S$ would be easy: Use $R$ to check for looping. if a loop is detected, reject; if no loop is detected, we can safely simulate $M$ and return what it returns. But last time we showed (by diagonalization) that $S$ does not exist. Therefore, $R$ cannot exist either."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Properties of runs\n",
    "\n",
    "The halting problem is a problem about the run of a particular machine $M$ on a particular $w$. There are lots of problems of this sort, but most have an extra wrinkle that involves creating a _third_ TM besides $R$ and $S$. Since it can be hard to keep track of them all, here's an example involving Python programs that hopefully is easier to follow.\n",
    "\n",
    "Let's show that it is undecidable whether a given Python program $P$ writes to the filesystem.\n",
    "\n",
    "Suppose, for the sake of contradiction, that this is decidable. That is, there exists a TM $R$ that accepts $\\langle P\\rangle$ if and only if $P$ would write to the filesystem. Let's call it the write-detector.\n",
    "\n",
    "We're going to build a universal decider $S$ that somehow uses the write-detector $R$ to decide $A_{\\mathsf{TM}}$. We assume the presence of a Python function `simulate` that simulates a TM and returns `True` for accept or `False` for reject or possibly loops.\n",
    "\n",
    "Then $S = $ “On input $\\langle M, w\\rangle$:\n",
    "\n",
    "1. Construct the Python program, called $P$:\n",
    "```\n",
    "    import os\n",
    "    if simulate(M, w):\n",
    "        os.system(\"rm -rf /\")\n",
    "```\n",
    "where `M` and `w` are filled in with data structures representing $M$ and $w$, respectively.\n",
    "2. Run $R$, the write-detector, on $P$.\n",
    "3. If $R$ detected a write, then _accept_.\n",
    "4. Otherwise, _reject_.\n",
    "\n",
    "The program $P$ acts as an \"adapter\" between the property we need to detect ($M$ accepting $w$) and the property that we can detect ($P$ writing to the filesystem).\n",
    "\n",
    "To see that $S$ is a universal decider, let's walk through the possible cases:\n",
    "- If $M$ accepts $w$, then $P$ would wipe out your files. $R$ detects this, and so $S$ accepts.\n",
    "- If $M$ rejects $w$, then $P$ does not wipe out your files. $R$ does not detect any writes, and so $S$ rejects.\n",
    "- Similarly, if $M$ loops on $w$, then $P$ would run forever but would not wipe out your files. $R$ does not detect any writes, and so $S$ rejects.\n",
    "\n",
    "Thus $S$ decides $A_{\\mathsf{TM}}$ as desired, which is a contradiction. We conclude that it's undecidable whether a given Python program writes to the filesystem.\n",
    "\n",
    "Hopefully, it's clear that there's a very wide variety of actions a machine/program can take that are undecidable to detect. (Your homework has one example of an action that _is_ decidable to detect, though.)\n",
    "\n",
    "**Question.** Try Problem 5.12: Show that it is undecidable whether a Turing machine ever erases a symbol (that is, overwrites a non-blank symbol with a blank symbol)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Properties of languages\n",
    "\n",
    "The next two examples in the book, Theorems 5.2 and 3, are slightly different. They are not questions about a single run of a machine, but about the _entire language_ that the machine recognizes. Theorem 5.2 is about whether the language is empty; Theorem 5.3 is about whether the language is regular.\n",
    "\n",
    "The basic shape of the proof is still the same. Assume that the question is decidable, so there is a TM $R$ that decides it. As before, we need to construct a new TM $S$ that decides $A_{\\mathsf{TM}}$. As before, $S$ has to construct an \"adapter\" (called $M_1$ or $M_2$ in the book) that links the question that $S$ wants to decide (does $M$ accept $w$?) with the question that $R$ has the magic ability to answer.\n",
    "\n",
    "Let's look at Theorem 5.2 first. Given $M$ and $w$, we can construct an adapter $M_1$ that recognizes a nonempty language iff $M$ accepts $w$.\n",
    "\n",
    "$M_1 =$ “On input $x$:\n",
    "\n",
    "1. If $x \\neq w$, _reject_.\n",
    "2. Otherwise, run $M$ on input $w$ and _accept_ if $M$ does.\n",
    "\n",
    "Let's think carefully about what $M_1$ would do.\n",
    "- If $M$ accepts $w$, then $M_1$ also accepts $w$ but rejects all $x \\neq w$. That is, $M_1$ recognizes $\\{w\\}$, a nonempty language.\n",
    "- If $M$ rejects $w$, then $M_1$ rejects both $w$ and all $x \\neq w$. That is, $M_1$ recognizes $\\emptyset$.\n",
    "- If $M$ loops on $w$, then $M_1$ also loops on $w$ and rejects all $x \\neq w$. So, $M_1$ recognizes $\\emptyset$.\n",
    "\n",
    "Finally, we define a universal decider $S =$ “On input $\\langle M, w\\rangle$:\n",
    "\n",
    "1. Construct $M_1$ as described above.\n",
    "2. Run $R$, the emptiness-detector, on $M_1$.\n",
    "3. If $R$ detected an empty language, _reject_.\n",
    "4. Otherwise, _accept_.\n",
    "\n",
    "Here's how $S$ works:\n",
    "- If $M$ accepts $w$, then $M_1$ would recognize $\\{w\\}$, a non-empty language, and so $S$ accepts.\n",
    "- If $M$ rejects or loops on $w$, then $M_1$ would recognize $\\emptyset$, and so $S$ rejects.\n",
    "\n",
    "Thus $S$ decides $A_{\\mathsf{TM}}$ as desired, which is a contradiction. We conclude that it's undecidable whether a given Turing machine recognizes the empty language."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "The scopes of the variables involved in the above proof can be confusing, so it might or might not help to look at the TMs as Python functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def is_empty(M): # This is R\n",
    "    \"\"\"Returns True iff M recognizes \\emptyset.\"\"\"\n",
    "    # Insert magic code here\n",
    "\n",
    "def accepts(M, w): # This is S\n",
    "    def M1(x):\n",
    "        \"\"\"Recognizes {w} if M(w) is True,\n",
    "           recognizes \\emptyset otherwise.\"\"\"\n",
    "        if x != w:\n",
    "            return False\n",
    "        else:\n",
    "            return M(w)\n",
    "    return not is_empty(M1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "The proof of Theorem 5.3 (regularity) is quite similar. Given $M$ and $w$, we can construct an adapter $M_2$ that recognizes a regular language iff $M$ accepts $w$.\n",
    "\n",
    "$M_2 =$ “On input $x$:\n",
    "\n",
    "1. If $x$ has the form $\\mathtt{0}^n\\mathtt{1}^n$, _accept_.\n",
    "2. Otherwise, run $M$ on input $w$ and _accept_ if $M$ does.\n",
    "\n",
    "Let's think carefully about what $M_2$ does.\n",
    "- If $M$ accepts $w$, then $M_2$ accepts all strings whether or not they are of the form $\\mathtt{0}^n\\mathtt{1}^n$. That is, it recognizes $\\Sigma^\\ast$, a regular language.\n",
    "- If $M$ rejects $w$, then $M_2$ accepts just strings of the form $\\mathtt{0}^n\\mathtt{1}^n$ and rejects all others. That is, it recognizes $\\{\\mathtt{0}^n \\mathtt{1}^n \\mid n \\geq 0\\}$, a non-regular language.\n",
    "- If $M$ loops on $w$, then $M_2$ accepts just strings of the form $\\mathtt{0}^n\\mathtt{1}^n$ and loops on all others. That is, it recognizes $\\{\\mathtt{0}^n \\mathtt{1}^n \\mid n \\geq 0\\}$, a non-regular language.\n",
    "\n",
    "The rest of the proof is very similar to the last one. We define a universal decider $S =$ “On input $\\langle M, w\\rangle$:\n",
    "\n",
    "1. Construct $M_2$ as described above.\n",
    "2. Run $R$, the regularity-detector, on $M_2$.\n",
    "3. If $R$ detected a regular language, _accept_.\n",
    "4. Otherwise, _reject_.\n",
    "\n",
    "Here's how $S$ works:\n",
    "- If $M$ accepts $w$, then $M_2$ would recognize $\\Sigma^\\ast$, a regular language, and so $S$ accepts.\n",
    "- If $M$ rejects or loops on $w$, then $M_2$ would recognize $\\{\\mathtt{0}^n \\mathtt{1}^n \\mid n \\geq 0\\}$, a non-regular language, and so $S$ rejects.\n",
    "\n",
    "Thus $S$ decides $A_{\\mathsf{TM}}$ as desired, which is a contradiction. We conclude that it's undecidable whether a given Turing machine recognizes a regular language."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "It turns out that there is a general recipe for proving results of this type. This is called Rice's Theorem and is the focus of one of the homework questions.\n",
    "\n",
    "**Question.** Try proving: It is undecidable whether two given Turing machines $M_1$ and $M_2$ recognize the same language."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Other undecidable problems\n",
    "\n",
    "Alas, we don't have time to look at more examples of undecidable problems. The examples we've looked at so far may seem a little arcane because they are all questions about Turing machines, but some other examples are:\n",
    "\n",
    "- Do two context-free grammars generate the same language (Exercise 5.1)?\n",
    "- The third and hardest puzzle we did on the first day of class (Section 5.2).\n",
    "- Does a polynomial equation in several variables have an integral solution?\n",
    "\n",
    "See [the survey by Poonen](http://www-math.mit.edu/~poonen/papers/sampler.pdf) for more examples."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Wednesday reading\n",
    "\n",
    "Optional reading: The rest of Section 5.1 and Section 5.2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Thursday class"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "source": [
    "Review for next Tuesday's midterm."
   ]
  }
 ],
 "metadata": {
  "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}