{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Week 8: Turing Machines" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from tock import *\n", "from IPython.display import IFrame, HTML" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Tuesday\n", "\n", "We have been climbing up the [Chomsky hierarchy](https://en.wikipedia.org/wiki/Chomsky_hierarchy) of language classes (cf. Figure 4.10):\n", "\n", "| Unit | Language class | Automaton | Grammar |\n", "|------|:------------------------------|:--------------------------|:-----------------------------|\n", "| III | Turing-recognizable languages | Turing machines | *Unrestricted grammars* |\n", "| | *Context-sensitive languages* | *Linear bounded automata* | *Context-sensitive grammars* |\n", "| II | Context-free languages | Pushdown automata | Context-free grammars |\n", "| I | Regular languages | Finite automata | Regular expressions |\n", "\n", "(Cells in italics are not core topics in this course, though we will mention them at some point.)\n", "\n", "Now we begin Unit III of the course and finally introduce Turing machines (TMs), which sit at the top of the hierarchy, because, as we will discuss at the end of today's lecture, we think Turing machines define what it is possible to compute." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Definition of Turing machines\n", "\n", "
Read both the informal and formal definitions of TMs (165–170). For now, you can skim or skip over the definition of configuration (page 168 at \"As a Turing machine computes\" through the end of page 169), though we will certainly need it later.
\n", "Watch W8E1: Turing Machines.
\n", "Read the book's examples of TMs (170–175).
\n", " \n", "q1 | [0] 0 |
q2 | ␣ [0] |
q3 | ␣ x [␣] |
q5 | ␣ [x] ␣ |
q5 | [␣] x ␣ |
q2 | ␣ [x] ␣ |
q2 | ␣ x [␣] |
accept | ␣ x ␣ [␣] |
accept
" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "run(m2, \"0 0\").only_path()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Machine $M_1$ recognizes the language $\\{w\\#w \\mid w \\in \\{\\texttt{0}, \\texttt{1}\\}^\\ast\\}$." ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "scrolled": true }, "outputs": [ { "data": { "image/svg+xml": [ "" ], "text/plain": [ "q1 | [0] 1 1 0 0 0 # 0 1 1 0 0 0 |
q2 | x [1] 1 0 0 0 # 0 1 1 0 0 0 |
q2 | x 1 [1] 0 0 0 # 0 1 1 0 0 0 |
q2 | x 1 1 [0] 0 0 # 0 1 1 0 0 0 |
q2 | x 1 1 0 [0] 0 # 0 1 1 0 0 0 |
q2 | x 1 1 0 0 [0] # 0 1 1 0 0 0 |
q2 | x 1 1 0 0 0 [#] 0 1 1 0 0 0 |
q4 | x 1 1 0 0 0 # [0] 1 1 0 0 0 |
q6 | x 1 1 0 0 0 [#] x 1 1 0 0 0 |
q7 | x 1 1 0 0 [0] # x 1 1 0 0 0 |
q7 | x 1 1 0 [0] 0 # x 1 1 0 0 0 |
q7 | x 1 1 [0] 0 0 # x 1 1 0 0 0 |
q7 | x 1 [1] 0 0 0 # x 1 1 0 0 0 |
q7 | x [1] 1 0 0 0 # x 1 1 0 0 0 |
q7 | [x] 1 1 0 0 0 # x 1 1 0 0 0 |
q1 | x [1] 1 0 0 0 # x 1 1 0 0 0 |
q3 | x x [1] 0 0 0 # x 1 1 0 0 0 |
q3 | x x 1 [0] 0 0 # x 1 1 0 0 0 |
q3 | x x 1 0 [0] 0 # x 1 1 0 0 0 |
q3 | x x 1 0 0 [0] # x 1 1 0 0 0 |
q3 | x x 1 0 0 0 [#] x 1 1 0 0 0 |
q5 | x x 1 0 0 0 # [x] 1 1 0 0 0 |
q5 | x x 1 0 0 0 # x [1] 1 0 0 0 |
q6 | x x 1 0 0 0 # [x] x 1 0 0 0 |
q6 | x x 1 0 0 0 [#] x x 1 0 0 0 |
q7 | x x 1 0 0 [0] # x x 1 0 0 0 |
q7 | x x 1 0 [0] 0 # x x 1 0 0 0 |
q7 | x x 1 [0] 0 0 # x x 1 0 0 0 |
q7 | x x [1] 0 0 0 # x x 1 0 0 0 |
q7 | x [x] 1 0 0 0 # x x 1 0 0 0 |
q1 | x x [1] 0 0 0 # x x 1 0 0 0 |
q3 | x x x [0] 0 0 # x x 1 0 0 0 |
q3 | x x x 0 [0] 0 # x x 1 0 0 0 |
q3 | x x x 0 0 [0] # x x 1 0 0 0 |
q3 | x x x 0 0 0 [#] x x 1 0 0 0 |
q5 | x x x 0 0 0 # [x] x 1 0 0 0 |
q5 | x x x 0 0 0 # x [x] 1 0 0 0 |
q5 | x x x 0 0 0 # x x [1] 0 0 0 |
q6 | x x x 0 0 0 # x [x] x 0 0 0 |
q6 | x x x 0 0 0 # [x] x x 0 0 0 |
q6 | x x x 0 0 0 [#] x x x 0 0 0 |
q7 | x x x 0 0 [0] # x x x 0 0 0 |
q7 | x x x 0 [0] 0 # x x x 0 0 0 |
q7 | x x x [0] 0 0 # x x x 0 0 0 |
q7 | x x [x] 0 0 0 # x x x 0 0 0 |
q1 | x x x [0] 0 0 # x x x 0 0 0 |
q2 | x x x x [0] 0 # x x x 0 0 0 |
q2 | x x x x 0 [0] # x x x 0 0 0 |
q2 | x x x x 0 0 [#] x x x 0 0 0 |
q4 | x x x x 0 0 # [x] x x 0 0 0 |
q4 | x x x x 0 0 # x [x] x 0 0 0 |
q4 | x x x x 0 0 # x x [x] 0 0 0 |
q4 | x x x x 0 0 # x x x [0] 0 0 |
q6 | x x x x 0 0 # x x [x] x 0 0 |
q6 | x x x x 0 0 # x [x] x x 0 0 |
q6 | x x x x 0 0 # [x] x x x 0 0 |
q6 | x x x x 0 0 [#] x x x x 0 0 |
q7 | x x x x 0 [0] # x x x x 0 0 |
q7 | x x x x [0] 0 # x x x x 0 0 |
q7 | x x x [x] 0 0 # x x x x 0 0 |
q1 | x x x x [0] 0 # x x x x 0 0 |
q2 | x x x x x [0] # x x x x 0 0 |
q2 | x x x x x 0 [#] x x x x 0 0 |
q4 | x x x x x 0 # [x] x x x 0 0 |
q4 | x x x x x 0 # x [x] x x 0 0 |
q4 | x x x x x 0 # x x [x] x 0 0 |
q4 | x x x x x 0 # x x x [x] 0 0 |
q4 | x x x x x 0 # x x x x [0] 0 |
q6 | x x x x x 0 # x x x [x] x 0 |
q6 | x x x x x 0 # x x [x] x x 0 |
q6 | x x x x x 0 # x [x] x x x 0 |
q6 | x x x x x 0 # [x] x x x x 0 |
q6 | x x x x x 0 [#] x x x x x 0 |
q7 | x x x x x [0] # x x x x x 0 |
q7 | x x x x [x] 0 # x x x x x 0 |
q1 | x x x x x [0] # x x x x x 0 |
q2 | x x x x x x [#] x x x x x 0 |
q4 | x x x x x x # [x] x x x x 0 |
q4 | x x x x x x # x [x] x x x 0 |
q4 | x x x x x x # x x [x] x x 0 |
q4 | x x x x x x # x x x [x] x 0 |
q4 | x x x x x x # x x x x [x] 0 |
q4 | x x x x x x # x x x x x [0] |
q6 | x x x x x x # x x x x [x] x |
q6 | x x x x x x # x x x [x] x x |
q6 | x x x x x x # x x [x] x x x |
q6 | x x x x x x # x [x] x x x x |
q6 | x x x x x x # [x] x x x x x |
q6 | x x x x x x [#] x x x x x x |
q7 | x x x x x [x] # x x x x x x |
q1 | x x x x x x [#] x x x x x x |
q8 | x x x x x x # [x] x x x x x |
q8 | x x x x x x # x [x] x x x x |
q8 | x x x x x x # x x [x] x x x |
q8 | x x x x x x # x x x [x] x x |
q8 | x x x x x x # x x x x [x] x |
q8 | x x x x x x # x x x x x [x] |
q8 | x x x x x x # x x x x x x [␣] |
accept | x x x x x x # x x x x x x ␣ [␣] |
accept
" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "run(m1, \"0 1 1 0 0 0 # 0 1 1 0 0 0\").only_path()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Writing Turing machines\n", "\n", "Read the subsection \"Terminology for Describing Turing Machines\" (184–185).
\n", "Read the rest of Section 3.3 (182–184).
\n", " \n", "