Turing機械

同義語：チューリング機械TuringマシンTuring machineTuring計算可能

概要

前提知識: 部分写像, 可算集合, μ再帰関数

「計算できる」とはどういうことか。1936 年に A. Turing は、紙と鉛筆で計算する人の動作を極限まで単純化した仮想の機械を考え、この問いに数学的な答えを与えた（OLT26 第 31 章の冒頭、p. 475）。機械は、マス目に区切られた両方向に無限に長いテープと、テープの 1 マスを読み書きするヘッドと、有限個の「状態」をもつ。各時点で、現在の状態と読んでいる記号だけから、書く記号・ヘッドを動かす向き・次の状態が決まる。これが Turing 機械 である。Turing 機械で計算できる関数は、関数を作る操作で定義した μ再帰関数とちょうど一致し、ほかに提案された計算の定義とも一致する。このことが「計算できる関数とは Turing 機械で計算できる関数のことである」という Church–Turingのテーゼの根拠になっている。
本記事では Turing 機械を定義し、計算がただ 1 通りに進むこと、加法を計算する機械が正しく働くことを証明する。さらに、Turing 機械は可算個しかないので、Turing 機械で計算できない関数 $\mathbb{N}\to\mathbb{N}$ が存在することを対角線論法で示す。
以下、$\mathbb{N}=\{0,1,2,\dots\}$、$\mathbb{Z}$ は整数全体とし、$1^n$ は記号 $1$ を $n$ 個並べた列（$1^0$ は空の列）を表す。

定義

Turing 機械

Turing 機械（Turing machine）とは、組 $M=(Q,\Gamma,\sqcup,q_0,\delta)$ であって次を満たすものをいう。

$Q$ は空でない有限集合で、その元を状態という。$q_0\in Q$ を 初期状態 という。
$\Gamma$ は有限集合で、その元を テープ記号 という。$\Gamma$ は 空白記号 $\sqcup$ と記号 $1$ を含む。
$\delta$ は $Q\times\Gamma$ から $Q\times\Gamma\times\{\mathrm{L},\mathrm{R},\mathrm{N}\}$ への部分写像で、遷移関数 という。$\delta(q,a)=(q',b,D)$ は「状態 $q$ で記号 $a$ を読んだら、そのマスに $b$ を書き、ヘッドを $D$ の向き（$\mathrm{L}$ は左、$\mathrm{R}$ は右、$\mathrm{N}$ は動かない）に 1 マス動かし、状態 $q'$ に移る」と読む。

様相と計算

$M=(Q,\Gamma,\sqcup,q_0,\delta)$ を Turing 機械とする。

写像 $\tau\colon\mathbb{Z}\to\Gamma$ で、有限個の $i$ を除いて $\tau(i)=\sqcup$ となるものを テープの内容 という。状態 $q$、テープの内容 $\tau$、ヘッドの位置 $h\in\mathbb{Z}$ の組 $(q,\tau,h)$ を様相（configuration）という。
様相 $C=(q,\tau,h)$ で $\delta(q,\tau(h))=(q',b,D)$ が定義されているとき、$C$ の 次の様相 を $(q',\tau',h+d)$ と定める。ここで $\tau'$ は $\tau'(h)=b$、$i\neq h$ では $\tau'(i)=\tau(i)$ となるテープの内容、$d$ は $D=\mathrm{L},\mathrm{R},\mathrm{N}$ に応じて $-1,1,0$ である。$\delta(q,\tau(h))$ が定義されていないとき、$C$ は 停止様相 であるという。
様相の列 $C_0,C_1,\dots$ で、各 $C_{j+1}$ が $C_j$ の次の様相であるものを計算という。$C_n$ が停止様相となる有限の列 $C_0,\dots,C_n$ があるとき、$M$ は $C_0$ から $n$ ステップで停止する という。

Turing 機械が計算する関数

$(x_1,\dots,x_k)\in\mathbb{N}^k$ に対し、テープの $0$ 番目のマスから右へ $1^{x_1}\sqcup1^{x_2}\sqcup\cdots\sqcup1^{x_k}$ と書き、ほかのマスはすべて空白としたテープの内容を $\tau_{\vec x}$ とする。$(q_0,\tau_{\vec x},0)$ を入力 $\vec x$ の 初期様相 という。
Turing 機械 $M$ が部分関数 $f\colon\mathbb{N}^k\rightharpoonup\mathbb{N}$ を 計算する とは、すべての $\vec x\in\mathbb{N}^k$ について次が成り立つことをいう。

$f(\vec x)$ が定義されて値 $y$ をとるなら、$M$ は初期様相から停止し、停止様相 $(q,\tau,h)$ のテープ $\tau$ はヘッドの位置から右へ $1^y$ が書かれ、ほかのマスはすべて空白である（$\tau(h+i)=1$（$0\le i< y$）、それ以外の $j$ で $\tau(j)=\sqcup$）。
$f(\vec x)$ が定義されないなら、$M$ は初期様相から停止しない。
ある Turing 機械が計算する部分関数を Turing 計算可能 な関数という。

テープを片側だけ無限にする、空白以外の記号を $1$ に限る、停止を専用の停止状態で表す、入出力を 2 進法で表すなど、細部の流儀は文献によって違う（OLT26 Definition 31.5–31.15、pp. 481–485 はテープを右にだけ無限とし、左端に印を置く）。しかし、こうした流儀の違いは Turing 計算可能な関数の全体を変えない（OLT26 §31.9、pp. 490–492）。本記事の流儀は、様相の定義が簡単になるように選んだ。

直感

Turing 機械は、計算する人の作業を「ノートの 1 マスを見る」「1 文字書き換える」「隣のマスへ目を移す」「頭の中の段階（状態）を切り替える」という最小の動作に分解したものである。状態が有限個なので、機械が一度に覚えておける情報は有限だが、テープは必要なだけ使える。計算の途中経過はすべてテープに書かれる。どの時点でも、状態と読んでいる記号だけで次の動作が決まるので、計算は機械的に進む。

例

後者関数を計算する機械

$Q=\{q_0,q_1,q_2\}$、$\Gamma=\{\sqcup,1\}$ とし、遷移関数を
$$ \delta(q_0,1)=(q_0,1,\mathrm{R}),\quad\delta(q_0,\sqcup)=(q_1,1,\mathrm{L}),\quad\delta(q_1,1)=(q_1,1,\mathrm{L}),\quad\delta(q_1,\sqcup)=(q_2,\sqcup,\mathrm{R}) $$
とする（$q_2$ では遷移が定義されない）。入力 $1^x$ に対し、機械は状態 $q_0$ で $1$ の列を右へ渡り、最初の空白（$x$ 番目のマス）に $1$ を書いて左へ戻り、状態 $q_1$ で $1$ の列を左へ渡って、$-1$ 番目の空白から右へ 1 マス戻り、$0$ 番目のマスで停止する。テープには $0$ 番目から $1^{x+1}$ が書かれているので、この機械は $S(x)=x+1$ を計算する。$x=0$ でも、$0$ 番目のマスに $1$ を書き、$-1$ 番目へ動いて戻るので正しく働く。

停止しない機械

$Q=\{q_0\}$、$\Gamma=\{\sqcup,1\}$、$\delta(q_0,a)=(q_0,a,\mathrm{R})$（$a\in\Gamma$）とすると、遷移関数がすべての組で定義されているので、どの様相も停止様相でなく、機械はどの入力からも停止しない。この機械はどこでも定義されない部分関数を計算する。

性質

計算の一意性と走査

計算の一意性

Turing 機械 $M$ と様相 $C_0$ に対し、$C_0$ から始まる計算はただ 1 通りに定まる。すなわち、停止しないなら無限列 $C_0,C_1,\dots$ がただ 1 つあり、停止するなら $C_n$ が停止様相となる列 $C_0,\dots,C_n$ がただ 1 つある。とくに、停止するかどうか、停止したときのテープの内容は $C_0$ だけで決まり、各 Turing 機械が計算する $k$ 変数の部分関数は、あってもただ 1 つである。

def-tm-configuration の 2 により、停止様相でない様相には次の様相がただ 1 つ定まり、停止様相には次の様相がない。$C_0,\dots,C_j$ が定まったとき、$C_j$ が停止様相でなければ $C_{j+1}$ はただ 1 つに定まり、停止様相なら列はそこで終わる。$j$ についての帰納法（再帰的定義の記事の定理「再帰定理」）により計算はただ 1 つに定まる。後半：停止様相は計算の中で高々 1 回、最後にだけ現れるので、停止するかどうかと停止様相は $C_0$ で決まる。初期様相は入力 $\vec x$ で決まるので、$M$ が部分関数 $f$ を計算するなら、$f(\vec x)$ は「初期様相から停止すれば停止様相のテープの $1$ の個数、停止しなければ定義されない」として $M$ と $\vec x$ だけから決まる。よって $f$ はただ 1 つである。$\square$

停止したときのテープが $1^y$ の形にならない入力がある機械は、def-tm-computes の意味ではどの $k$ 変数の部分関数も計算しない。
機械の正しさを示すときは、「同じ記号が並んだ区間を同じ状態のまま渡る」動作をまとめて扱うと便利である。

走査の補題

Turing 機械の状態 $q$ と記号 $a$ について $\delta(q,a)=(q,a,\mathrm{R})$ とする。様相 $(q,\tau,h)$ で $\tau(h)=\tau(h+1)=\cdots=\tau(h+m-1)=a$（$m\ge0$）ならば、$m$ ステップ後の様相は $(q,\tau,h+m)$ である。$\delta(q,a)=(q,a,\mathrm{L})$ で $\tau(h)=\tau(h-1)=\cdots=\tau(h-m+1)=a$ なら、$m$ ステップ後の様相は $(q,\tau,h-m)$ である。

$m$ についての帰納法による。$m=0$ なら明らかである。$m$ で成り立つとし、$\tau(h),\dots,\tau(h+m)$ がすべて $a$ とする。帰納法の仮定により $m$ ステップ後の様相は $(q,\tau,h+m)$ であり、$\tau(h+m)=a$ なので次の様相は $(q,\tau',h+m+1)$、ただし $\tau'$ は $h+m$ 番目に $a$ を書いたもので $\tau'=\tau$ である。左向きも同様である。$\square$

加法を計算する機械

加法機械の正しさ

$Q=\{q_0,q_1,q_2,q_3,q_4\}$、$\Gamma=\{\sqcup,1\}$ とし、遷移関数を次で定める（ほかの組では定義しない）。
$$ \begin{aligned} &\delta(q_0,1)=(q_0,1,\mathrm{R}),&&\delta(q_0,\sqcup)=(q_1,1,\mathrm{R}),&&\delta(q_1,1)=(q_1,1,\mathrm{R}),\\ &\delta(q_1,\sqcup)=(q_2,\sqcup,\mathrm{L}),&&\delta(q_2,1)=(q_3,\sqcup,\mathrm{L}),&&\delta(q_3,1)=(q_3,1,\mathrm{L}),\\ &\delta(q_3,\sqcup)=(q_4,\sqcup,\mathrm{R}).&&&& \end{aligned} $$
この機械 $M_+$ は加法 $(x,y)\mapsto x+y$ を計算する。

入力 $(x,y)$ の初期様相では、$0,\dots,x-1$ 番目が $1$、$x$ 番目が空白、$x+1,\dots,x+y$ 番目が $1$ で、ほかは空白である。計算を 5 つの段階に分けて追う。
段階 1：lem-tm-scan（$q_0$、記号 $1$、右向き）により、$x$ ステップ後の様相は状態 $q_0$、位置 $x$ で、テープは変わらない。$x$ 番目は空白なので、次のステップで $x$ 番目に $1$ を書き、状態 $q_1$、位置 $x+1$ になる。この時点でテープは $0,\dots,x+y$ 番目が $1$、ほかは空白である。
段階 2：lem-tm-scan（$q_1$、右向き）により、$y$ ステップ後に状態 $q_1$、位置 $x+y+1$ になる。そこは空白なので、次のステップで状態 $q_2$、位置 $x+y$ になる（テープは変わらない）。
段階 3：$x+y$ 番目は $1$ なので、次のステップでそこを空白に書き換え、状態 $q_3$、位置 $x+y-1$ になる。テープは $0,\dots,x+y-1$ 番目が $1$、ほかは空白である。
段階 4：$x+y-1,x+y-2,\dots,0$ 番目の $x+y$ 個のマスはすべて $1$ なので、lem-tm-scan（$q_3$、左向き）により $x+y$ ステップ後に状態 $q_3$、位置 $-1$ になる（$x+y=0$ なら段階 3 の直後にすでに位置 $-1$ にいる）。
段階 5：$-1$ 番目は空白なので、次のステップで状態 $q_4$、位置 $0$ になる。$q_4$ では遷移が定義されないので、これは停止様相である。
停止様相のテープは $0$ 番目から右へ $1^{x+y}$ が書かれ、ほかは空白で、ヘッドは $0$ 番目にある。よって def-tm-computes の 1 が成り立つ。加法は全域的なので 2 は考えなくてよい。全体のステップ数は $(x+1)+(y+1)+1+(x+y)+1=2x+2y+4$ である。$\square$

この機械は、2 つの $1$ の列の間の空白を $1$ で埋め、最後の $1$ を 1 つ消すことで足し算をしている。OLT26 Example 31.12（p. 483）も同じ考え方の機械を与えている。

計算できない関数の存在

Turing 機械は有限個のデータで決まるので、本質的に可算個しかない。これに対し、関数 $\mathbb{N}\to\mathbb{N}$ は非可算個ある。したがって計算できない関数がある。対角線論法を使えば、その具体的な形も書ける。
状態とテープ記号の名前を付け替えても、機械の動作は変わらない。正確には、全単射 $\alpha\colon Q\to Q'$、$\beta\colon\Gamma\to\Gamma'$（$\beta(\sqcup)=\sqcup'$、$\beta(1)=1$）で $M$ の遷移関数を写した機械 $M'$ は、様相 $(q,\tau,h)$ を $(\alpha(q),\beta\circ\tau,h)$ に写すと計算の各ステップがそのまま対応するので、$M$ と同じ部分関数を計算する。そこで、$Q$ と $\Gamma$ が $\mathbb{N}$ の有限部分集合で、空白記号が $0$、記号 $1$ が $1$ である機械を 標準の機械 とよぶ。どの機械も、名前の付け替えで同じ部分関数を計算する標準の機械に移せる（OLT26 §32.2、pp. 497–498）。

Turing 計算可能でない関数の存在

標準の機械全体の集合は可算である。したがって Turing 計算可能な 1 変数の部分関数全体は可算である。
標準の機械を（重複を許して）$M_0,M_1,M_2,\dots$ と並べ、$M_n$ が計算する 1 変数の部分関数を $\varphi_n$ とする（$M_n$ が何も計算しないときは、どこでも定義されない関数とする）。このとき
$$ f(n):=\begin{cases}\varphi_n(n)+1&(\varphi_n(n)\text{ が定義されるとき})\\0&(\text{そうでないとき})\end{cases} $$
で定まる全域関数 $f\colon\mathbb{N}\to\mathbb{N}$ は Turing 計算可能でない。

1：標準の機械 $M=(Q,\Gamma,0,q_0,\delta)$ は、$Q=\{s_1,\dots,s_a\}$、$\Gamma=\{c_1,\dots,c_b\}$、$q_0$、および $\delta$ の定義されている組の一覧 $\delta(q,c)=(q',c',D)$（$D=\mathrm{L},\mathrm{R},\mathrm{N}$ を $0,1,2$ で表す）を並べた自然数の有限列
$$ (a,s_1,\dots,s_a,b,c_1,\dots,c_b,q_0,\ q,c,q',c',D,\ \dots) $$
で決まる。自然数の有限列に対し、それがこの形で標準の機械を表していればその機械を、そうでなければ ex-tm-loop の機械（を標準の機械にしたもの）を対応させる写像は、自然数の有限列全体から標準の機械全体への全射である。自然数の有限列全体は可算なので（可算集合の記事の例「自然数の有限列の全体」）、標準の機械全体も可算である（可算集合の記事の系「像と単射による可算性の伝播」）。Turing 計算可能な部分関数はどれも標準の機械が計算するので、その全体は標準の機械全体の像として可算である。
2：$f$ を計算する Turing 機械 $M$ があったとする。$M$ を名前の付け替えで標準の機械に移すと、それはある $M_e$ であり、$\varphi_e=f$ である。$f$ は全域的なので $\varphi_e(e)$ は定義され、$f(e)=\varphi_e(e)+1\neq\varphi_e(e)$ となって、$\varphi_e=f$ に反する。$\square$

1 と、関数 $\mathbb{N}\to\{0,1\}$ 全体が非可算であること（可算集合の記事の系「自然数の冪集合の非可算性」）からも、Turing 計算可能でない関数（とくに $\{0,1\}$ に値をとる関数）が存在することが分かる（OLT26 Theorem 32.1、p. 498）。2 は対角線論法（Cantorの対角線論法）でそれを具体的に構成している。ただし、標準の機械の並べ方 $M_0,M_1,\dots$ を計算できる形で選んでも、$f$ を計算することはできない。並べ方が計算できる形なら、$\varphi_n(n)$ が定義されるかどうかが分かれば $M_n$ を動かして $f(n)$ を求められるので、この定理は、その判定を機械的に行えないことを示している。これと近い、$M_n$ が入力 $n$ で停止するかどうかを判定する Turing 機械がないという主張と、それから導かれる、一般の機械と入力の組について停止を判定できないという主張が停止問題の決定不能性である（OLT26 Lemma 32.7・Theorem 32.8、pp. 501–502）。

変種と頑健性

Turing 機械にはさまざまな変種がある。テープを複数本にする、テープを 2 次元の格子にする、テープ記号を $\sqcup$ と $1$ の 2 種類に限る、テープを片側だけ無限にする、などである。どの変種でも Turing 計算可能な関数の全体は変わらない。たとえば 2 本のテープをもつ機械は、1 本のテープの偶数番目のマスを 1 本目、奇数番目のマスを 2 本目に使い、2 つのヘッドの位置を印の記号で記録することで、1 本のテープの機械で模倣できる（OLT26 §31.9、pp. 490–492。この記事では証明しない）。遷移を関数でなく関係にした 非決定性 Turing 機械 は、計算量の理論で重要な役割を果たす（同所）。
計算できる関数の定義としての Turing 機械の強さは、ほかの定義との一致からも裏付けられる。

原始再帰関数はすべて Turing 計算可能である（Bil03 Theorem 13.4、p. 89。この記事では証明しない）。
Turing 計算可能な部分関数の全体は、μ再帰関数の全体と一致する（Gal15 §7.7.1、p. 355。全域関数については Bil03 Theorem 13.14・Theorem 14.8・Corollary 14.9、pp. 92–97。この記事では証明しない）。Turing 機械の計算は様相の列として自然数で符号化でき、「$s$ は機械 $M$ の入力 $x$ での停止する計算の記録である」という関係は原始再帰的になる。そこから μ 作用素で計算の記録を探せば、計算される関数が μ再帰関数であることが分かる（μ再帰関数の記事の定理「Kleene の標準形定理」と同じ考え方）。
すべての Turing 機械を模倣する 1 台の機械 万能 Turing 機械 が存在する（OLT26 §32.3、pp. 499–500、Bil03 Corollary 14.13、p. 98。この記事では証明しない）。詳しくは万能Turing機械の記事の主題である。
こうした一致が、「直観的に計算できる関数は Turing 計算可能である」という Church–Turingのテーゼの根拠になっている（OLT26 §31.10、pp. 492–493）。テーゼは「直観的に計算できる」という数学的に定義されていない概念を含むので、定理として証明されるものではない。

仮定を外したときの反例

外す条件	反例	成り立たなくなること
遷移が部分写像（各組で次の動作が高々 1 つ）	$(q_0,1)$ に対して $(q_0,1,\mathrm{R})$ と $(q_1,1,\mathrm{N})$ の 2 つの動作を許す機械	計算の一意性（prop-tm-deterministic）
状態の集合が有限	状態を無限個 $q_0,q_1,\dots$ もつ「機械」	計算できない関数の存在（thm-tm-uncomputable）：任意の $g\colon\mathbb{N}\to\mathbb{N}$ が計算できてしまう
ヘッドが左にも動ける（右と停留だけにする）	後者関数 $S(x)=x+1$	計算できること：右と停留だけの機械では $x\ge1$ で $S$ を計算できない

反例の確かめ

1 行目：様相 $(q_0,\tau,h)$ で $\tau(h)=1$ のとき、次の様相が $(q_0,\tau,h+1)$ と $(q_1,\tau,h)$ の 2 通りになり、計算は 1 通りに定まらない。
2 行目：状態 $q_n$（$n\in\mathbb{N}$）と $r_n$（$n\in\mathbb{N}$）を用意し、$\delta(q_n,1)=(q_{n+1},\sqcup,\mathrm{R})$、$\delta(q_n,\sqcup)=(r_{g(n)},\sqcup,\mathrm{N})$、$\delta(r_{m+1},\sqcup)=(r_m,1,\mathrm{L})$、$\delta(r_{m+1},1)=(r_m,1,\mathrm{L})$、$\delta(r_0,a)=(r_0',a,\mathrm{R})$（$r_0'$ では停止）とする。入力 $1^x$ を消しながら右へ進むと状態 $q_x$ で $x$ 番目のマスに着き、状態 $r_{g(x)}$ に移る。そこから $1$ を書きながら $g(x)$ マス左へ進むと $x-g(x)+1,\dots,x$ 番目に $1$ が並び、状態 $r_0$ で $x-g(x)$ 番目にいる。最後に 1 マス右へ動いて停止すると、ヘッドから右へ $1^{g(x)}$ が書かれている（$g(x)=0$ なら何も書かずに停止する）。よって状態が無限個あれば、どんな関数 $g$ も「計算」できる。
3 行目：ヘッドが右か停留にしか動かない機械が、入力 $1^x$（$x\ge1$）から停止して $1^{x+1}$ を出力したとする。ヘッドは $0$ 番目から始まって左へ動かないので、停止時の位置 $h$ は $h\ge0$ であり、$h$ より右のマスは一度も訪れていないので初期のままである。出力の形から $h+1,\dots,h+x$ 番目が $1$ でなければならないが、初期のテープで $1$ があるのは $0,\dots,x-1$ 番目だけなので、$h+x\le x-1$、すなわち $h\le-1$ となり矛盾する。ex-tm-successor の機械は、書いた $1$ の列の左端まで戻るために左へ動いている。