{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "# Week 10: 2018/04/01-05\n",
    "\n",
    "## Monday\n",
    "\n",
    "Read Section 5.1. This is a difficult section, so read it carefully. But we probably won't do Theorems 5.10, 5.13 in detail."
   ]
  },
  {
   "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": [
    "### Reducibility\n",
    "\n",
    "In general, to show that some problem P is undecidable, you assume that P is decidable by some TM $R$ and use that to implement a universal decider $S$. That implementation usually has three steps:\n",
    "\n",
    "1. Convert an input to $S$ (a pair $\\langle M, w\\rangle$) into an instance of P.\n",
    "2. Run $R$ on the converted instance.\n",
    "3. Interpret the result of $R$ to decide whether $M$ accepts $w$. \n",
    "\n",
    "In the reduction from $A_{\\textsf{TM}}$ to the halting problem, step 1 was trivial: $\\langle M, w \\rangle$ maps to itself. But in other cases, this step may be more complicated. \n",
    "\n",
    "For example, 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 can't possibly feed $\\langle M, w\\rangle$ to $R$ because $R$ wants a Python program. So we need to convert $M$ and $w$ into a Python program. We assume a Python function `simulate` that simulates a TM and returns `True` for accept or `False` for reject; this function can also potentially loop. It should be obvious that such a function exists, although it's long enough that we don't bother to write it out.\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",
    "In general, when you're trying to prove that detecting property P is undecidable, this \"adapter\" usually has to do the following things:\n",
    "- Simulate $M$ on $w$.\n",
    "- If $M$ accepts, then exhibit property P.\n",
    "- If $M$ rejects, then don't exhibit property P.\n",
    "- You must also set it up so that if $M$ loops, property P is not exhibited.\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": [
    "Sometimes, the existence of a Turing machine simulator is not so obvious, and we have to think more carefully about it.\n",
    "\n",
    "**Question**. An _unrestricted grammar_ is like a CFG, but the left-hand sides can be strings. A derivation starts with $S$ and continues until no more rules can be applied. Show that it is undecidable whether an unrestricted grammar generates a nonempty language. Hint: Convert $\\langle M, w\\rangle$ to a grammar whose starting rule is\n",
    "$$ S \\rightarrow q_0 w $$\n",
    "and for each transition of $M$, create a grammar rule (or rules) to simulate that transition.\n",
    "\n",
    "Some other examples of undecidable problems are:\n",
    "\n",
    "- Do two context-free grammars generate the same language (Exercise 5.1)?\n",
    "- Post's Correspondence Problem (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": [
    "## Thursday class"
   ]
  },
  {
   "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 5.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}}$. The first thing that $S$ needs to do is to convert $\\langle M, w\\rangle$ to just a machine (called $M_1$ or $M_2$ in the book). We have to take care to construct this \"adapter\" machine to link 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$. We're going to construct $M_1$ differently from the book; if you like the book's version better, that's fine too.\n",
    "\n",
    "$M_1 =$ “On input $x$:\n",
    "\n",
    "1. Run $M$ on input $w$.\n",
    "2. If $M$ accepts $w$, then _accept_ $x$.\n",
    "3. If $M$ rejects $w$, then _reject_ $x$.\n",
    "\n",
    "Let's think carefully about what $M_1$ would do.\n",
    "- If $M$ accepts $w$, then $M_1$ accepts all strings $x$. That is, $M_1$ recognizes $\\Sigma^\\ast$, a nonempty language.\n",
    "- If $M$ rejects $w$, then $M_1$ rejects all strings $x$. That is, $M_1$ recognizes $\\emptyset$.\n",
    "- If $M$ loops on $w$, then $M_1$ also loops on all strings $x$. 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 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$. Again, we'll do this a little differently from the book.\n",
    "\n",
    "$M_2 =$ “On input $x$:\n",
    "\n",
    "1. Run $M$ on input $w$.\n",
    "2. If $M$ accepts $w$, and $x$ has the form $\\mathtt{0}^n\\mathtt{1}^n$, _accept_ $x$.\n",
    "3. Otherwise, _reject_ $x$.\n",
    "\n",
    "Let's think carefully about what $M_2$ does.\n",
    "- If $M$ accepts $w$, then $M_2$ accepts strings $x$ of the form $\\mathtt{0}^n\\mathtt{1}^n$. So it recognizes a non-regular language.\n",
    "- If $M$ rejects $w$, then $M_2$ rejects all strings $x$. So it recognizes $\\emptyset$, a regular language.\n",
    "- If $M$ loops on $w$, then $M_2$ also loops on all strings $x$. So it recognizes $\\emptyset$, a 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, _reject_.\n",
    "4. Otherwise, _accept_.\n",
    "\n",
    "Here's how $S$ works:\n",
    "- If $M$ accepts $w$, then $M_2$ would recognize $\\{\\mathtt{0}^n\\mathtt{1}^n\\}$, a non-regular language, and so $S$ accepts.\n",
    "- If $M$ rejects or loops on $w$, then $M_2$ would recognize $\\emptyset$, a 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": {},
   "source": [
    "**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": [
    "We've tried to follow a general recipe for proving undecidability results. It turns out that this recipe can be distilled into a catch-all theorem called Rice's Theorem: any property of a language recognized by a Turing machine, as long as the property is not always true or always false, is undecidable.\n",
    "\n",
    "There are some properties of the internal working of a Turing machine that are decidable (you'll see one in HW7). But broadly speaking, questions about behaviors of computer programs tend to be undecidable. When you see problems like this in real life -- and you definitely will -- you should smell undecidability and think twice before trying to implement a solution to the problem."
   ]
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}