停止問題

同義語：halting problem停止問題の決定不能性

概要

前提知識: Turing機械, 万能Turing機械, μ再帰関数

Turing 機械に入力を与えて動かすと、いつか停止することもあれば、永久に動き続けることもある。では、機械の番号と入力を受け取り、その機械がその入力で停止するかどうかを必ず正しく答えて停止する機械は作れるだろうか。これが 停止問題（halting problem）であり、答えは否定的である。停止するかどうかは、実際に動かしてみれば「停止する」側だけは確かめられるが、「停止しない」側を有限の時間で確かめる一般的な方法はない。
この記事では、停止する組の集合が決定可能でないこと（停止問題の決定不能性）を対角線論法で証明する。さらに、その集合は半決定可能であるがその補集合は半決定可能でないこと、集合が決定可能であることは集合と補集合がともに半決定可能であることと同値であることを示し、停止までのステップ数を計算可能な関数で上から押さえられないことを導く。

記法と前提

記法は万能Turing機械の記事に合わせる。$\mathbb{N}=\{0,1,2,\dots\}$、$M_e$ は番号 $e$ の機械（同記事の定義「番号から決まる機械」）、「入力 $x$ で停止する」とは入力 $x$ の初期様相から停止すること（Turing機械の記事の定義「様相と計算」「Turing 機械が計算する関数」）とする。万能Turing機械の記事の定義「1 ステップの関数」の原始再帰的な関係 $\operatorname{Hlt}(e,k)$（$k$ が表す様相が $M_e$ の停止様相であること）と、同記事の節「万能関数は μ再帰関数である」で定めた、計算を $s$ ステップ進めた様相の符号 $\operatorname{conf}(e,x,s)$（原始再帰関数）を使う。
次の 2 つの事実を使う。どちらもこの記事では証明しない。

(A) 計算のモデルの一致．Turing 計算可能な部分関数の全体と μ再帰関数（部分関数を含む）の全体は、変数の個数ごとに一致する（Gal15 §7.7.1、p. 355。全域関数については Bil03 Theorem 13.14（p. 92）、Theorem 14.8・Corollary 14.9（p. 97））。万能Turing機械の記事の定理「万能 Turing 機械の存在」の証明で使われているものと同じである。以下、「μ再帰関数は Turing 計算可能である」向きを (A1)、「Turing 計算可能な部分関数は μ再帰関数である」向きを (A2) と書く。
(B) 機械の番号．1 変数の Turing 計算可能な部分関数 $f$ には、$M_e$ が $f$ を計算するような番号 $e$ がある（Turing機械の記事の節「計算できない関数の存在」の名前の付け替えと、万能Turing機械の記事の補題「標準の機械はどれも番号をもつ」）。これは上の 2 つの記事で証明されている。
(A) により、μ再帰関数が合成・原始再帰・μ 作用素で閉じていることは、Turing 計算可能な部分関数についても成り立つ。

定義

決定可能と半決定可能

$A\subset\mathbb{N}^k$ とする。

$A$ の特性関数 $\chi_A$ が Turing 計算可能であるとき、$A$ は 決定可能（decidable、計算可能）であるという。
$A$ がある Turing 計算可能な部分関数 $f\colon\mathbb{N}^k\rightharpoonup\mathbb{N}$ の定義域であるとき、$A$ は 半決定可能（semi-decidable）であるという。

半決定可能な集合は、計算可能枚挙（computably enumerable）、帰納的可算（recursively enumerable）ともよばれる。空でない半決定可能な集合は計算可能な全域関数の値域として並べ上げられ、この言い換えが「枚挙」の名の由来である（OLT26 Theorem 30.9、p. 455。この記事では証明しない）。(A) により、定義の「Turing 計算可能」は「μ再帰的」に置き換えてよい。決定可能な $A$ は μ再帰関数の記事の意味の再帰的な関係である。

停止問題

$$ H:=\{(e,x)\in\mathbb{N}^2\mid M_e\text{ は入力 }x\text{ で停止する}\},\qquad K:=\{e\in\mathbb{N}\mid(e,e)\in H\} $$
とおく。$H$ を 停止集合、$K$ を 自己停止集合 という。$H$ が決定可能かどうかという問いを 停止問題 という。

停止したときのテープの形は問わない。万能Turing機械の記事の万能関数 $u(e,x)$ は、停止したテープが形の正しい $1^y$ のときだけ値をもつので、その定義域は $H$ に含まれるが、一般には $H$ より小さい（同記事の例「停止しない番号と形の正しくない出力」の 2）。

例

停止するかどうかの例

万能Turing機械の記事の例「後者関数の機械の番号と模倣」の番号 $e_S$（Turing機械の記事の例「後者関数を計算する機械」の機械）について、すべての $x$ で $(e_S,x)\in H$ である。
万能Turing機械の記事の例「停止しない番号と形の正しくない出力」の 1 の番号 $e$（Turing機械の記事の例「停止しない機械」の機械）について、どの $x$ でも $(e,x)\notin H$ である。
万能Turing機械の記事の例「停止しない番号と形の正しくない出力」の 2 の番号 $e'$ では、すべての $x$ で $(e',x)\in H$ だが、$u(e',x)$ が定義されるのは $x\le1$ のときだけである。

個々の機械については、このように停止するかどうかが分かることも多い。停止問題が問うのは、すべての番号と入力に対して一様に答える 1 つの手順があるかどうかである。
停止までのステップ数を区切れば、判定はできる。

計算の記録と停止

すべての $e,x,s$ について、$\operatorname{Hlt}(e,\operatorname{conf}(e,x,s))$ が成り立つことは、$M_e$ が入力 $x$ で $s$ ステップ以内に停止することと同値である。とくに
$$ H_{\le}:=\{(e,x,s)\mid M_e\text{ は入力 }x\text{ で }s\text{ ステップ以内に停止する}\} $$
は決定可能であり、$(e,x)\in H\iff\exists s\,\bigl((e,x,s)\in H_{\le}\bigr)$ である。

$M_e$ の入力 $x$ からの計算を $C_0,C_1,\dots$ とする。万能Turing機械の記事の定理「万能関数の標準形」の証明の段 1 により、$C_s$ が存在すれば $\operatorname{conf}(e,x,s)$ は $C_s$ を表し、計算が $C_n$（$n< s$）で停止していれば $\operatorname{conf}(e,x,s)=\operatorname{conf}(e,x,n)$ である。$s$ ステップ以内に停止するなら、停止様相 $C_n$（$n\le s$）を表す $\operatorname{conf}(e,x,s)=\operatorname{conf}(e,x,n)$ について、同記事の補題「1 ステップの関数の正しさ」により $\operatorname{Hlt}$ が成り立つ。$s$ ステップ以内に停止しないなら、$C_s$ は存在して停止様相でなく、同じ補題により $\operatorname{Hlt}$ は成り立たない。
$\operatorname{Hlt}$ は原始再帰的な関係、$\operatorname{conf}$ は原始再帰関数なので、$H_{\le}$ の特性関数 $(e,x,s)\mapsto\chi_{\operatorname{Hlt}}(e,\operatorname{conf}(e,x,s))$ は原始再帰関数であり、(A1) により Turing 計算可能である。最後の主張は定義から明らかである。$\square$

停止問題の決定不能性

自己停止集合 $K$ と停止集合 $H$ は、どちらも決定可能でない。すなわち、入力 $(e,x)$ に対して、$M_e$ が入力 $x$ で停止するなら $1$、停止しないなら $0$ を出力して必ず停止する Turing 機械は存在しない。

$K$ について． $K$ が決定可能だとすると、$\chi_K$ は Turing 計算可能なので、(A2) により μ再帰関数である。全域関数 $g(x,s):=\chi_K(x)$ に μ 作用素を施して
$$ d(x):\simeq\mu s\,[\,g(x,s)=0\,] $$
とおく。$g$ は全域的なので、$d(x)$ は $\chi_K(x)=0$ のとき $0$ で、$\chi_K(x)=1$ のとき定義されない。すなわち、$d(x)$ が定義されるのは $x\notin K$ のときちょうどである。$d$ は μ再帰関数なので、(A1) により Turing 計算可能であり、(B) により $M_e$ が $d$ を計算する番号 $e$ がある。Turing機械の記事の定義「Turing 機械が計算する関数」により、$M_e$ は $d(x)$ が定義されるとき停止し、定義されないとき停止しない。したがってすべての $x$ について
$$ (e,x)\in H\iff d(x)\text{ が定義される}\iff x\notin K\iff(x,x)\notin H $$
である。$x=e$ とおくと $(e,e)\in H\iff(e,e)\notin H$ となり、矛盾する。
$H$ について． $H$ が決定可能なら、$\chi_K(x)=\chi_H(x,x)$ は Turing 計算可能な関数と $x\mapsto(x,x)$ の合成なので Turing 計算可能になり、前半に反する。$\square$

証明の要は、「自分の番号を入力されたときに停止するかどうか」を反転させる機械 $M_e$ を作り、それに自分自身の番号を与えることである。これは Cantorの対角線論法と同じ形をしている。行を機械 $M_0,M_1,\dots$、列を入力 $0,1,\dots$ として「停止する・しない」の表を作ると、$d$ は対角線を反転したものであり、どの行とも対角線のところで食い違う。停止の判定ができるなら $d$ が計算でき、表のどこかの行に現れるはずなので矛盾する。
万能Turing機械の記事の定理「万能関数の全域的な延長の不存在」の後の注意も、同じ結論を別の道筋で述べている。そこでは、停止の判定ができれば万能関数を全域的な計算可能関数に延長できてしまうことから矛盾を導いている。

半決定可能性

停止問題は決定できないが、「停止する」側は確かめられる。

停止集合は半決定可能

$H$ と $K$ は半決定可能である。

$h(e,x):\simeq\mu s\,\bigl[\,1\mathbin{\dot-}\chi_{\operatorname{Hlt}}(e,\operatorname{conf}(e,x,s))=0\,\bigr]$ とおく。μ 作用素を施す関数は原始再帰関数なので全域的であり、$h$ は μ再帰関数である。lem-hp-record により、$h(e,x)$ が定義されるのは、ある $s$ で $M_e$ が入力 $x$ で $s$ ステップ以内に停止するとき、すなわち $(e,x)\in H$ のときちょうどであり、そのとき値は停止までのステップ数である。(A1) により $h$ は Turing 計算可能なので、$H=\operatorname{dom}h$ は半決定可能である。$K$ は $x\mapsto h(x,x)$ の定義域である。$\square$

$h$ を計算する機械は、番号 $e$ の機械を入力 $x$ で 1 ステップずつ動かし、停止したらそのステップ数を出力する。停止しなければ $h$ を計算する機械も停止しない。これが「動かしてみれば停止する側だけは確かめられる」ことの正確な形である。lem-hp-record と合わせると、$H$ は決定可能な集合 $H_{\le}$ の射影であり、「ステップ数 $s$ が存在する」という量化記号 1 つが決定不能性を生んでいる。

決定可能性と半決定可能性

$A\subset\mathbb{N}$ について、$A$ が決定可能であることと、$A$ と補集合 $\mathbb{N}\setminus A$ がともに半決定可能であることは同値である。

決定可能なら：$\chi_A$ は (A2) により μ再帰関数で、$f(x):\simeq\mu s\,[\,1\mathbin{\dot-}\chi_A(x)=0\,]$ は $x\in A$ のときちょうど定義される μ再帰関数である。(A1) により Turing 計算可能なので、$A$ は半決定可能である。$\chi_{\mathbb{N}\setminus A}=1\mathbin{\dot-}\chi_A$ も Turing 計算可能なので、補集合も同様である。
逆を示す。$A=\operatorname{dom}f$、$\mathbb{N}\setminus A=\operatorname{dom}g$（$f,g$ は Turing 計算可能）とし、(B) により $M_{e_1}$ が $f$ を、$M_{e_2}$ が $g$ を計算する番号 $e_1,e_2$ をとる。Turing機械の記事の定義「Turing 機械が計算する関数」により、$x\in A$ は $M_{e_1}$ が入力 $x$ で停止することと、$x\notin A$ は $M_{e_2}$ が入力 $x$ で停止することと同値である。
$$ t(x):\simeq\mu s\,\bigl[\,\bigl(1\mathbin{\dot-}\chi_{\operatorname{Hlt}}(e_1,\operatorname{conf}(e_1,x,s))\bigr)\cdot\bigl(1\mathbin{\dot-}\chi_{\operatorname{Hlt}}(e_2,\operatorname{conf}(e_2,x,s))\bigr)=0\,\bigr] $$
とおく。どの $x$ も $A$ か $\mathbb{N}\setminus A$ に属するので、どちらかの機械が停止し、lem-hp-record により $t$ は全域的な μ再帰関数である。
$$ \chi_A(x)=\chi_{\operatorname{Hlt}}\bigl(e_1,\operatorname{conf}(e_1,x,t(x))\bigr) $$
を示す。$x\in A$ なら、$x\notin\mathbb{N}\setminus A$ なので $M_{e_2}$ は入力 $x$ で停止せず、$t(x)$ は $M_{e_1}$ が $t(x)$ ステップ以内に停止する最小の $s$ であり、右辺は $1$ である。$x\notin A$ なら $M_{e_1}$ は停止しないので、lem-hp-record により右辺は $0$ である。右辺は μ再帰関数の合成なので、(A1) により $\chi_A$ は Turing 計算可能である。$\square$

証明の手順は、2 台の機械を交互に 1 ステップずつ動かし、先に停止したほうで答えを決めるものである。片方だけでは、停止しないときに答えが出ない。

停止しない側は半決定可能でない

$\mathbb{N}\setminus K$ と $\mathbb{N}^2\setminus H$ は半決定可能でない。

$\mathbb{N}\setminus K$ が半決定可能なら、thm-hp-semidecidable と thm-hp-post により $K$ は決定可能になり、thm-hp-undecidable に反する。$\mathbb{N}^2\setminus H=\operatorname{dom}g$（$g$ は Turing 計算可能）なら、$\mathbb{N}\setminus K=\operatorname{dom}(x\mapsto g(x,x))$ は半決定可能になり、前半に反する。$\square$

帰結

停止時間は計算可能な関数で押さえられない

全域的な Turing 計算可能関数 $b\colon\mathbb{N}^2\to\mathbb{N}$ で、$(e,x)\in H$ ならば $M_e$ が入力 $x$ で $b(e,x)$ ステップ以内に停止するようなものは存在しない。

そのような $b$ があったとする。$(e,x)\in H$ なら $M_e$ は $b(e,x)$ ステップ以内に停止し、$(e,x)\notin H$ ならどのステップ数でも停止しないので、lem-hp-record により
$$ \chi_H(e,x)=\chi_{\operatorname{Hlt}}\bigl(e,\operatorname{conf}(e,x,b(e,x))\bigr) $$
である。$b$ は (A2) により μ再帰関数なので、右辺は全域的な μ再帰関数であり、(A1) により $\chi_H$ は Turing 計算可能になって thm-hp-undecidable に反する。$\square$

言い換えると、どんな計算可能な関数 $b$ をとっても、$b(e,x)$ ステップより長く動いてから停止する組 $(e,x)$ がある。停止するまで待つ時間を前もって計算で見積もることはできない。

停止を判定できない 1 台の機械

thm-hp-semidecidable により $K=\operatorname{dom}f$ となる Turing 計算可能な $f$ があり、(B) により $f$ を計算する機械 $M_{e_0}$ がある。この 1 台の機械について、$\{x\mid(e_0,x)\in H\}=K$ は決定可能でない。停止問題の難しさは、無限個の機械を相手にすることから来るだけでなく、1 台の機械の中にすでに現れる。

ほかの決定不能な問題

停止問題は、ほかの問題が決定可能でないことを示す出発点になる。問題 $B$ を解く手順から停止問題を解く手順が作れれば、$B$ も決定可能でない。この方法で次のことが示される。いずれもこの記事では証明しない。

Rice の定理．1 変数の部分計算可能関数（μ再帰的な部分関数）の標準的な番号付け $\varphi_0,\varphi_1,\varphi_2,\dots$（OLT26 第 30 章）をとる。部分計算可能関数の集まり $\mathcal{C}$ が空でもなく部分計算可能関数の全体でもないなら、番号の集合 $\{e\in\mathbb{N}\mid\varphi_e\in\mathcal{C}\}$ は決定可能でない（OLT26 Theorem 30.23、p. 465）。たとえば $\{e\mid\varphi_e(0)\text{ が定義される}\}$ や $\{e\mid\varphi_e\text{ は全域的}\}$ は決定可能でない。ここでの番号 $e$ は関数 $\varphi_e$ の番号であり、この記事の機械の番号 $M_e$ とは別のものである。機械 $M_e$ は形の正しくない出力で停止することがあるので（ex-hp-examples の 3）、$M_e$ に「計算する関数」が定まるとは限らない。
一階論理の決定問題．一階述語論理の文が妥当かどうか（すべての構造で真かどうか）を判定する Turing 機械は存在しない（OLT26 Theorem 32.16、p. 511）。一方、Gödelの完全性定理により妥当な文は証明を数え上げて見つけられるので、妥当な文の集合は半決定可能である（同 Theorem 32.18、p. 512）。有限のモデルをもつかどうかも決定できない（同 Theorem 32.21、p. 514、Trakhtenbrot の定理）。

反例：条件を外すと成り立たない

外す条件	反例	成り立たなくなること
停止までのステップ数に上限がない	上限 $s$ も入力する $H_{\le}$	決定不能性
すべての番号の機械を相手にする	停止しない機械 1 台の番号 $e$ を固定した $\{x\mid(e,x)\in H\}=\emptyset$	決定不能性
状態の集合が有限	状態を無限個もつ「機械」	$\chi_K$ が計算できないこと

反例の確かめ

1 行目：lem-hp-record により $H_{\le}$ は決定可能である。
2 行目：ex-hp-examples の 2 の機械では、どの $x$ でも停止しないので、集合は空で決定可能である。ただし ex-hp-single-machine のように、1 台の機械を固定しても決定可能でない場合がある。どの番号で決定可能になるかは、機械によって違う。
3 行目：Turing機械の記事の反例の確かめの 2 行目は、状態を無限個許すと任意の関数 $g\colon\mathbb{N}\to\mathbb{N}$ を「計算」する機械が作れることを示している。$g=\chi_K$ にとれば、自己停止集合の特性関数も「計算」できてしまう。thm-hp-undecidable の証明が使ったのは、機械が有限のデータで決まり番号 $e$ をもつこと（(B)）である。

表の行は条件を外す例であるが、条件はそのままで対象の集合を取り替えると、成り立つことが変わる場合もある。$K$ は半決定可能だが（thm-hp-semidecidable）、補集合 $\mathbb{N}\setminus K$ は半決定可能でない（cor-hp-complement）。停止する側と停止しない側は対称でない。

補足

Church–Turing のテーゼとの関係．この記事の定理は、Turing 機械と μ再帰関数という数学的に定義された計算のモデルについての定理である。「停止を判定する機械的な手順はどんな形でも存在しない」と読むには、直観的に計算できる関数は Turing 計算可能であるという Church–Turingのテーゼを認める必要がある。テーゼは定義されていない概念を含むので定理ではない。
文献での定式化．OLT26 Definition 32.4・32.5（p. 501）は、機械と入力を受け取り、停止するかどうかを答える問題として停止問題を定式化し、Lemma 32.7・Theorem 32.8（pp. 501–502）でその決定不能性を示している。μ再帰関数の番号付けで同じことを述べたものが OLT26 Theorem 30.6（p. 452）、Theorem 30.11・30.12（p. 458）、Corollary 30.15（p. 460）である。