{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"deletable": true,
"editable": true
},
"source": [
"# Week 8: 2017/03/20-24"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false,
"deletable": true,
"editable": true
},
"outputs": [],
"source": [
"from tock import *"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": true,
"editable": true
},
"source": [
"## Monday reading\n",
"\n",
"Read Section 3.1 and 3.3."
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": true,
"editable": true
},
"source": [
"## Tuesday class\n",
"\n",
"### Turing machines, finally\n",
"\n",
"By now, the definition of Turing machines (TMs) should be easy to understand. But pay special attention to the distinction between _Turing-recognizable_ (a.k.a. \"recursively enumerable\" or \"computably enumerable\") and _(Turing-)decidable_ (a.k.a. \"recursive\" or \"computable\"). When a TM runs on an input string, there are three possible outcomes: halt and accept, halt and reject, and loop (which is treated as a reject).\n",
"\n",
"We distinguish between two kinds of TMs: TMs and _decider_ TMs. A TM can accept, reject, or loop on a string, whereas a decider TM must either accept or reject, but never loop. Then, a language $L$ is Turing-recognizable iff there is a TM that accepts all and only the strings in $L$. And $L$ is (Turing-)decidable iff there is a decider TM that accepts all and only the strings in $L$.\n",
"\n",
"This is a distinction we haven't worried about in the past. Why? Deterministic FAs and PDAs always halt, so there's no distinction between accepting and deciding. Nondeterministic FAs and PDAs can have $\\varepsilon$ loops, but it's easy to change such machines into an equivalent ones that do not loop. So the distinction is unimportant. With Turing machines (which are deterministic unless stated otherwise), the distinction is _extremely_ important."
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": true,
"editable": true
},
"source": [
"There are many variations out there in the definition of TM. Be careful if you refer to other sources. We're going to allow one small extension to Sipser's definition. In Sipser's definition, $\\delta(q, a) = (r, b, d)$, where $d \\in \\{\\text{L}, \\text{R}\\}$. Following Turing's original definition, we'll also allow $d = \\text{N}$, which means \"no move\"."
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": true,
"editable": true
},
"source": [
"### Examples: formal descriptions\n",
"\n",
"Here are the book's two examples of formal descriptions. Apologies that the notation used here is slightly different from Sipser's: it uses a caret (`^`) to specify the movement of the head. So $a \\rightarrow \\hat{} b$ means \"read $a$, write $b$, and move left,\" while $a \\rightarrow b \\hat{}$ means \"read $a$, write $b$, and move right.\" And $a \\rightarrow b$ means \"read $a$, write $b$, and don't move.\""
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false,
"deletable": true,
"editable": true
},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"m2 = read_csv(\"tm-m2.csv\")\n",
"m2"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false,
"deletable": true,
"editable": true
},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"run(m2, \"0 0 0 0\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": true,
"editable": true
},
"source": [
"Since the machine is deterministic, the run is easier to view as a list of configurations, so we'll write a little function to do that:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false,
"deletable": true,
"editable": true
},
"outputs": [],
"source": [
"def print_run(*args):\n",
" r = run(*args)\n",
" for c in r.only_path():\n",
" print(c)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"q1,[0] 0 0 0\n",
"q2,_ [0] 0 0\n",
"q3,_ x [0] 0\n",
"q4,_ x 0 [0]\n",
"q3,_ x 0 x ^\n",
"q5,_ x 0 [x]\n",
"q5,_ x [0] x\n",
"q5,_ [x] 0 x\n",
"q5,[_] x 0 x\n",
"q2,_ [x] 0 x\n",
"q2,_ x [0] x\n",
"q3,_ x x [x]\n",
"q3,_ x x x ^\n",
"q5,_ x x [x]\n",
"q5,_ x [x] x\n",
"q5,_ [x] x x\n",
"q5,[_] x x x\n",
"q2,_ [x] x x\n",
"q2,_ x [x] x\n",
"q2,_ x x [x]\n",
"q2,_ x x x ^\n",
"accept,_ x x x _ ^\n"
]
}
],
"source": [
"print_run(m2, \"0 0 0 0\")"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false,
"deletable": true,
"editable": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"q1,[0] 0 0\n",
"q2,_ [0] 0\n",
"q3,_ x [0]\n",
"q4,_ x 0 ^\n",
"reject,_ x 0 _ ^\n"
]
}
],
"source": [
"print_run(m2, \"0 0 0\")"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false,
"deletable": true,
"editable": true
},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"m1 = read_csv(\"tm-m1.csv\")\n",
"m1"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": true,
"editable": true
},
"source": [
"Note that in this example, the reject state has been omitted. If at any point in the run, there is no transition defined for the current state and symbol, the machine rejects. You can do this when you write formal descriptions of TMs also."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false,
"deletable": true,
"editable": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"q1,[0] 1 0 # 0 1 0\n",
"q2,x [1] 0 # 0 1 0\n",
"q2,x 1 [0] # 0 1 0\n",
"q2,x 1 0 [#] 0 1 0\n",
"q4,x 1 0 # [0] 1 0\n",
"q6,x 1 0 [#] x 1 0\n",
"q7,x 1 [0] # x 1 0\n",
"q7,x [1] 0 # x 1 0\n",
"q7,[x] 1 0 # x 1 0\n",
"q1,x [1] 0 # x 1 0\n",
"q3,x x [0] # x 1 0\n",
"q3,x x 0 [#] x 1 0\n",
"q5,x x 0 # [x] 1 0\n",
"q5,x x 0 # x [1] 0\n",
"q6,x x 0 # [x] x 0\n",
"q6,x x 0 [#] x x 0\n",
"q7,x x [0] # x x 0\n",
"q7,x [x] 0 # x x 0\n",
"q1,x x [0] # x x 0\n",
"q2,x x x [#] x x 0\n",
"q4,x x x # [x] x 0\n",
"q4,x x x # x [x] 0\n",
"q4,x x x # x x [0]\n",
"q6,x x x # x [x] x\n",
"q6,x x x # [x] x x\n",
"q6,x x x [#] x x x\n",
"q7,x x [x] # x x x\n",
"q1,x x x [#] x x x\n",
"q8,x x x # [x] x x\n",
"q8,x x x # x [x] x\n",
"q8,x x x # x x [x]\n",
"q8,x x x # x x x ^\n",
"accept,x x x # x x x _ ^\n"
]
}
],
"source": [
"print_run(m1, \"0 1 0 # 0 1 0\")"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false,
"deletable": true,
"editable": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"q1,[0] 1 0 # 0 1 1\n",
"q2,x [1] 0 # 0 1 1\n",
"q2,x 1 [0] # 0 1 1\n",
"q2,x 1 0 [#] 0 1 1\n",
"q4,x 1 0 # [0] 1 1\n",
"q6,x 1 0 [#] x 1 1\n",
"q7,x 1 [0] # x 1 1\n",
"q7,x [1] 0 # x 1 1\n",
"q7,[x] 1 0 # x 1 1\n",
"q1,x [1] 0 # x 1 1\n",
"q3,x x [0] # x 1 1\n",
"q3,x x 0 [#] x 1 1\n",
"q5,x x 0 # [x] 1 1\n",
"q5,x x 0 # x [1] 1\n",
"q6,x x 0 # [x] x 1\n",
"q6,x x 0 [#] x x 1\n",
"q7,x x [0] # x x 1\n",
"q7,x [x] 0 # x x 1\n",
"q1,x x [0] # x x 1\n",
"q2,x x x [#] x x 1\n",
"q4,x x x # [x] x 1\n",
"q4,x x x # x [x] 1\n",
"q4,x x x # x x [1]\n"
]
}
],
"source": [
"print_run(m1, \"0 1 0 # 0 1 1\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"*Question*. Try writing a (formal description of) a TM that decides the language $\\{\\texttt{a}^{2n} \\mid n \\geq 0\\}$.\n",
"\n",
"*Question*. Try writing a TM (first informal, then formal description) that decides the language $\\{ww^R \\mid w \\in \\{\\texttt{0},\\texttt{1}\\}^\\ast\\}$."
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": true,
"editable": true
},
"source": [
"### Macros\n",
"\n",
"Writing Turing machines is extremely tedious -- much more so than assembly language. To reduce the tedium, many textbooks introduce the idea of _macros_. In the state transition diagram of a TM, a node can be labeled with the name of _another TM_. If machine $M$ reaches a node labeled with another TM $M'$, then $M'$ is run until it reaches its accept state; then control returns to $M$ right where it left off. Note that this is not really an extension of the TM formalism; it's just a shorthand for writing repetitive machines more compactly.\n",
"\n",
"For example, in $M_1$ above, the same subgraph appears twice (states $q_2, q_4$ are the same as states $q_3, q_5$). So we could simplify it to:\n",
"\n",
"where $M'$ is:\n",
""
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": true,
"editable": true
},
"source": [
"However, Sipser does not use notation like this for macros. Instead, he quickly graduates you from formal descriptions of machines to _implementation-level descriptions_. These are like pseudocode. But they still speak in terms of the head moving on the tape and reading and writing symbols on the tape. They shouldn't, for example, make use of variables or arithmetic. See the examples in the book to get an idea of what is allowed and what isn't.\n",
"\n",
"It's common to use macros in implementation-level descriptions, too: if you define a TM $M'$, then in the course of defining $M$, you can write \"simulate $M'$.\""
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": true,
"editable": true
},
"source": [
"### The Church-Turing thesis\n",
"\n",
"Recall that Turing's original paper (1936) proposed Turing machines as a model of what _humans_ do when they compute. He imagined a computing person in an idealized scenario:\n",
"\n",
"- He has an infinitely long paper tape, divided into squares.\n",
"- He can write one symbol in each square, and the number of possible symbols is finite (e.g., `0` to `9`).\n",
"- He can only look at a finite number of squares at a time. \n",
"- He can only move a finite distance at a time.\n",
"- He has only a finite number of “states of mind.”\n",
"\n",
"Basically this is an appeal to intuition that when people compute, this is what they do. Furthermore, he had to argue (quite briefly) that Turing machines can perform any such computation. This came to be known as the Church-Turing thesis (CTT).\n",
"\n",
"One [brief statement](http://www.alanturing.net/turing_archive/archive/l/l32/L32-005.html) of the thesis: \"[Turing] machines can do anything that could be described as 'rule of thumb' or 'purely mechanical'.\" [Elsewhere](http://www.turingarchive.org/viewer/?id=149&title=14), he characterized these problems as \"those problems which can be solved by human clerical labour, working to fixed rules, and without understanding.\""
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": true,
"editable": true
},
"source": [
"## Wednesday reading\n",
"\n",
"Read Section 3.2."
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": true,
"editable": true
},
"source": [
"## Thursday class\n",
"\n",
"An additional argument made for the Church-Turing thesis is \"robustness\" -- lots of different extensions of Turing machines have been proposed, and while they make writing Turing machine programs more convenient, they can be shown not to increase their power.\n",
"\n",
"**Question.** Name every possible thing you could imagine adding to a Turing machine to make it more powerful.\n",
"\n",
"First of all, there are some extensions in Turing's image of a human computer:\n",
"\n",
"- He is allowed to look at multiple (but finitely many) squares at a time.\n",
"- He is allowed to move multiple (but finitely many) squares to the left or right.\n",
"- Furthermore, Turing also mentions the possibility of a two-dimensional grid.\n",
"\n",
"It is easy to convert a TM which can look at multiple squares or move multiple squares into a standard TM by adding more states. A two dimensional grid can be simulated in a manner similar to multiple tapes (see below).\n",
"\n",
"The book discusses two bigger extensions which are used later: multiple tapes, and nondeterminism. Multiple tapes are described clearly enough in the book; a few comments here on nondeterminism.\n",
"\n",
"### Nondeterminism\n",
"\n",
"We can make Turing machines nondeterministic, similarly to how we made finite automata nondeterministic. Remarkably, NTMs are no more powerful than TMs. But if it were possible to build a real NTM, it would be useful for all kinds of very very practical things, because it would be (we think) so much faster than a deterministic TM. That speed difference is the focus of Unit Four.\n",
"\n",
"When defining NTMs, we must pay attention to the distinction between recognizing and deciding. A NTM accepts a string iff at least one branch of the computation accepts it. The other branches can reject or loop. A NTM is a _decider_ iff _all_ of its branches halt (not loop).\n",
"\n",
"So a NTM recognizes a language $L$ iff for each string $w \\in L$, there is at least one branch that accepts $w$, and the other branches either reject or loop on $w$; and for each string $w \\notin L$, all branches either reject or loop on $w$. And a decider NTM decides a language $L$ iff for each string $w \\in L$, there is at least one branch that accepts $w$, and the other branches reject $w$; and for each string $w \\notin L$, all branches reject $w$.\n",
"\n",
"The proof of Theorem 3.16 treats the computation as a directed tree. Each node is a configuration, and each edge is a step of the computation. The simulating DTM does a breadth-first search (BFS) on this tree. Each node in the tree is given an address (known as a Gorn address), which is stored on tape 3. The proof is a little bit unclear on one point: Stage 4 just says \"Replace the string on tape 3 with the next string in the string ordering,\" but doesn't explain what the ordering is -- it's the order defined on page 14, which causes the addresses to be listed in breadth-first order.\n",
"\n",
"### Alternatives\n",
"\n",
"Taking the robustness argument further, we can argue that many alternative definitions of computability have been proposed, alternatives that look radically different from Turing machines, and those, too, can be shown to be equivalent to Turing machines. These are mentioned at the end of Section 3.2. The most important ones are probably:\n",
"\n",
"- The [untyped lambda calculus](https://en.wikipedia.org/wiki/Lambda_calculus)\n",
"- [Partial recursive functions](https://en.wikipedia.org/wiki/Μ-recursive_function)\n",
"- [Unrestricted grammars](https://en.wikipedia.org/wiki/Unrestricted_grammar)\n",
"\n",
"[Accidentally Turing Complete](http://beza1e1.tuxen.de/articles/accidentally_turing_complete.html) is a collection of other weird things that are equivalent to TMs."
]
}
],
"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
}