コンピューターでは解けない問題

1. 計算できるのかできないのか、それが問題だ

1.1. 停止性問題

前章では、計算時間を考えました。そこでの大前提は、与えられた問題がコンピューターで計算できるということでした。計算できるのだけど、どのくらい時間がかかるのかを問題にしていた訳です。しかし、与えられた問題は、そもそもコンピューターで計算できるのでしょうか？

この根本的な問題に取り組んだのが、イギリスの数学者アラン・チューリングです。チューリングは1936年の論文で、今日「停止性問題」と呼ばれる問題と本質的に同じ問題を扱い、それを判定するアルゴリズムが存在しないことを証明しました（呼び名の由来は、この節の後半のコラムを参照してください）。

ここで、アルゴリズムまたは、それを実装したプログラムが存在するといったときには、以下の仮定を置くことにします。

計算時間や記憶容量は、有限であればいくらでも使って良い
想定範囲のすべての入力に対して必ず停止し結果を出力する

（本来は厳密な計算モデルを定義するのですが、詳細な定義をすることなく前章で紹介したRAMモデルを仮定します。RAMモデルで計算できることは、この後で紹介するチューリングマシンでも計算でき、その逆も成り立ちます。かかる時間は違っても「計算できるかどうか」の結論は変わらないので、この章ではどちらのモデルで考えても同じです。）

停止性問題

入力： プログラム $P$ と、プログラム $P$ への入力データ $x$

出力：

プログラム $P$ が入力 $x$ に対して停止するときは「停止する」を出力して停止
プログラム $P$ が入力 $x$ に対して停止しないときは「停止しない」を出力して停止

この問題は、入力として与えられたプログラムが、「停止するか？」という問いに対して、停止するなら Yes、停止しないなら No と出力する問題とみることができます。このように Yes または No で答えられるような問題を決定問題といいます。

\[\def\Hp{\mathsf{Halt}} \def\Dh{P_{\mathsf{H}}}\]

停止性判定をするプログラムが計算する関数を、「停止」を意味する単語 halt を用いて $\Hp(P, x)$ と表すことにし、次のように定義します。

\[\Hp(P,x)=\begin{cases} \text{停止する}, & \text{プログラム $P$ が入力 $x$ で停止するとき}\\ \text{停止しない}, & \text{プログラム $P$ が入力 $x$ で停止しないとき} \end{cases}\]

この関数を計算するプログラム（以下、停止判定プログラム Halt とよびます）を図にすると、次のようになります。問題は、このようなプログラムが本当に作れるかどうかです。

図 1. 停止判定プログラム Halt の入出力

【「停止性問題」という名前の由来】

チューリングの1936年の論文には、「停止性問題（halting problem）」という言い方は出てきません。彼が論じたのは、機械が数字を限りなく印字し続けられるか、特定の記号をいつか印字するか、といった形の問題でした。「機械はいつか止まるか」という今日の形に近い述べ方は、クリーネの1952年の教科書に見られます。halting problem（停止性問題）という名前は、アメリカの数学者マーティン・デイヴィスが1952年ごろの講義で使いはじめ、1958年の著書 Computability and Unsolvability で広く知られるようになったとされています。証明の中心にある、機械を自分自身の記述に適用するアイデアはチューリングの論文にすでにありますが、私たちが教わる問題の形と呼び名は、後の世代が整えたものなのです。

出典：S. Lucas, The origins of the halting problem（2021年）

チューリングマシン：計算のいちばん単純なモデル

チューリングは、紙と鉛筆で計算する人の作業を、次の部品だけでできた仮想の機械に置き換えて考えました。これをチューリングマシンといいます。

テープ：マス目に区切られ、左右にいくらでも続く記録用の帯です。各マスに記号が1つ書かれています（ここでは0か1）。
ヘッド：テープの1マスを指し、そのマスの記号を読んだり書き換えたりします。
状態：機械がいま「どの段階の作業中か」を表す、有限個の印です（A、B、…と「停止」）。
規則表：「状態Aで記号0を読んだら、1を書き、右に1マス動き、状態Bに移る」のような規則の一覧です。

機械は1ステップごとに、いまの状態とヘッドの下の記号から規則表の行を1つ選び、その行のとおりに動きます。「停止」の状態に移ったところで計算が終わります。

図 2. チューリングマシンの部品と1ステップの動き

部品はこれだけですが、チューリングマシンは、今日のコンピューターで計算できることを（時間はかかっても）すべて計算できると考えられています。「機械的な手順で計算できるものは、チューリングマシンで計算できるものと一致する」という考え方をチャーチ＝チューリングのテーゼといいます。証明された定理ではなく、「計算できる」という直感的な概念の定義として広く受け入れられている主張です。後で紹介するビジービーバー（対角線論法の節の最後のコラム）も、チューリングマシンを使って定義されます。

プログラムを入力とすることについて

この問題設定は不自然でしょうか。実は、プログラムはコンピューターのメモリ上では、他のデータと同じ数値で表現されたデータに過ぎません。そのため、プログラムを他のデータと同じく、入力として与えることは不自然なことではありません。

そのようなプログラムの実例として、以下のようなものがあります。

コンパイラー — プログラムを読み込み、コンピューターが解釈できる機械語に変換するプログラムです。これは、プログラムを入力として受け取るプログラムです。
エミュレーター — 1983年に発売されたファミコンは、カートリッジの形になったゲームプログラムを与えることで動作しました。ファミコンのエミュレーターは、ファミコン動作を模倣するプログラム（エミュレーター）の入力に、ゲームプログラムを与えることによって動作するプログラムです。

このように、あるプログラムを実行する際に、別のプログラムを入力として与えることは、珍しいことではありません。

また、プログラムにはバグがつきもので、一文字のミスであっても致命的です。もし、そのミスによって、いつまでも結果がでないことがあれば、そのようなプログラムは実行したくありません。もし、作ったプログラム $P$ と、その入力データ $x$ を与えると、あらかじめ停止するかどうかを教えてくれるようなプログラムが存在すると役に立ちそうです。

任意のプログラムと入力の組み合わせについて

後で登場する対角線論法では、すべてのプログラムを $P_1, P_2, P_3, \ldots$ と番号付けし、それぞれに任意のプログラムを入力として与えます。ここで、いくつかの疑問が生じるかもしれません。

疑問1：構文的に正しくない文字列も「プログラム」として扱うのか？

コンピューター上では、プログラムは文字の並び（文字列）として保存されています。したがって、すべての有限長の文字列を列挙すれば、その中に「正しいプログラム」も「意味不明な文字列」も含まれます。

構文的に正しくない文字列を実行しようとすると、インタプリタやコンパイラは構文エラーを出して停止します。これも「停止」の一種と考えます。つまり、「停止する」とは「有限時間で計算が終了する」ことであり、正常終了かエラー終了かは問いません。

疑問2：整数を期待するプログラムに、別のプログラムを入力として与えてよいのか？

ここでも同じ考え方が適用できます。プログラム $P$ が整数を期待しているのに、別のプログラム $Q$ の文字列表現を入力として与えた場合、通常は型エラーや実行時エラーが発生して停止します。これも「停止する」として扱います。

より厳密には、すべての入力を「文字列」として統一的に扱い、プログラム側が必要に応じてその文字列を解釈する、という立場をとります。

具体例 — Pythonインタプリタで考える

Pythonインタプリタは任意の文字列を入力として受け取ることができます。

正しいPythonプログラムなら → 実行して結果を出力（停止 or 無限ループ）
構文エラーがあれば → SyntaxError を出して停止
実行時にエラーが起きれば → TypeError 等を出して停止

このように、どのような入力を与えても「停止する」か「停止しない」かのいずれかになります。

停止の統一的な定義

以上を踏まえ、この章では「停止する」を次のように定義します。

プログラムが停止するとは、正常終了・異常終了・エラー終了を問わず、有限時間で計算が終了することをいう。

この定義のもとでは、プログラムと入力の任意の組み合わせに対して、結果は必ず「停止する」か「停止しない」のいずれかになります。

このような扱いが可能なのは、万能チューリングマシン（または万能インタプリタ）の存在によります。万能チューリングマシンとは、任意のチューリングマシン $M$ の符号化（文字列表現）と入力 $x$ を受け取り、$M$ が $x$ に対して行う計算をシミュレートできる特別なチューリングマシンです。

現代のコンピューターは、この万能チューリングマシンの実現です。プログラムもデータも同じメモリ上に格納され、同じビット列として扱われるというプログラム内蔵方式（フォン・ノイマン・アーキテクチャ）がこれを可能にしています。

1.2. 停止性の具体例

具体的な例を考えてみましょう。プログラム $P_1$ を挿入ソートのプログラム、入力 $x$ を数字の並び $\langle 9, 1, 4, 3, 7, 6, 2, 3\rangle$ とすれば、$P_1$ は入力 $x$ を整列した結果を出力してから停止することはすでに前章で学んだとおりです。つまり、

\[\Hp(P_1,\langle 9, 1, 4, 3, 7, 6, 2, 3\rangle)=\text{停止する}\]

となります。

では、入力によって停止したり停止しなかったりするプログラムとは、どのようなプログラムでしょう。次のような動作をするプログラム $P_2$ を考えます。

プログラム $P_2$

入力：整数 $n$

変数 $x=0$ とする
変数 $x$ の現在の値に $n$ を加えて、それを新たな $x$ の値にする（$x\leftarrow x+n$）
$x < 10$ ならば、2行目に戻る。$x\geq 10$ なら、4行目に進む。
$x$ の値を出力して停止

実行例1： このプログラム $P_2$ の入力が $n=4$ のとき、$x$ の値は初期化の後、プログラムの2,3が繰り返し実行されて、$0 \rightarrow 4 \rightarrow 8 \rightarrow 12$ と変化し、$10$ 以上になった時点で、$12$ を表示して停止します。

実行例2： このプログラム $P_2$ の入力に $n=-1$ を与えると、$x$ の値は $0 \rightarrow -1 \rightarrow -2 \rightarrow -3 \rightarrow \cdots$ と減り続け、プログラムの 2,3 の部分を永久に繰返すことになります。（ここでは、現実のコンピューターと異なり、どのような大きな整数でも扱えることを仮定しています。もし、現実的に整数の値範囲を制限したとしても、入力を $n=0$ とすれば、やはり停止しない状況をつくることができます。）

よって、

\[\begin{align*} \Hp(P_2,4) & = \text{停止する} \\ \Hp(P_2,-1)& = \text{停止しない} \end{align*}\]

となります。

$P_2$ のようなプログラムであれば、中身を見れば停止しないケースがわかりますし、停止性問題を解くアルゴリズムを作れそうな気がします。ここで、難しいのはどのようなプログラム$P$と、その入力データ $x$に対しても停止性を判定するようなアルゴリズムを作らなくてはならないことです。

1.3. 【定理】停止性問題は計算不可能

ここでは、どのようなプログラム $P$ とその入力 $x$ の組に対しても停止性関数 $\Hp(P,x)$ を計算してくれるようなアルゴリズムが存在しないことを証明します。

証明の戦略：背理法

この証明では背理法を使います。背理法とは、示したいことの反対をいったん仮定し、そこから矛盾を導くことで、「その仮定は誤りだった」と結論する論法です。

身近な例にアリバイがあります。「Aさんが犯人だ」と仮定すると、Aさんは犯行時刻に現場にいたはずです。ところが、その時刻にAさんが遠く離れた町で大勢に目撃されていたなら、矛盾が生じます。よって「Aさんは犯人ではない」と結論できます。

停止性問題の証明は、次の4段階で進みます。

仮定：どんなプログラム $P$ と入力 $x$ に対しても正しく答える停止判定プログラム Halt が存在する、と仮定する。
構成：Halt を部品として、Halt の答えと逆のことをする「天邪鬼（あまのじゃく）」プログラム $\Dh$ を作る。
自己適用：$\Dh$ に、$\Dh$ 自身を入力として与える。
矛盾：Halt の答えが「停止する」でも「停止しない」でも矛盾が起きる。よって1の仮定が誤りで、Halt は存在しない。

この論法は、後の節で説明する対角線論法と同じしくみです。

証明（段階1・2：仮定と構成）

まず、関数 $\Hp(P,x)$ を計算するアルゴリズムが存在すると仮定します。すると、$\Hp(P,x)$ を用いた次のような、プログラム $P$ を入力とするプログラム $\Dh$ が作れます。

図 3. 停止判定プログラムHaltを部品にした天邪鬼プログラム $\Dh$ の構成

このプログラム $\Dh$ は、次のような動作をします。

プログラム $\Dh$ の動作

入力： プログラム $P$

処理：

入力として受け取ったプログラム $P$ をコピーしてから $\Hp(P,P)$ を計算する
結果が「$\Hp(P,P)=\text{停止する}$」の場合
プログラム $\Dh$ 自体は永久に停止しないように、無限の繰り返し処理（無限ループ）を実行する
結果が「$\Hp(P,P)=\text{停止しない}$」の場合
プログラム $\Dh$ の実行を直ちに終了する

$\Dh$ は、とても変なプログラムです。しかし、重要なのは、仮に関数 $\Hp(P,x)$ を計算するアルゴリズムが存在すれば、プログラム $\Dh$ を作るのはとても簡単だということです。Halt を呼び出して、その答えで分岐するだけなので、数行で書けます。つまり、$\Dh$ が存在することは、段階1の仮定から直接出てきます。

矛盾の導出（段階3・4：自己適用と矛盾）

ここで、プログラム $\Dh$ の入力に $\Dh$ 自身を与えます。 $\Dh$ もプログラムなので、その文字列を入力データとして渡すことができます（プログラムを入力とすることについては前の節を参照）。このとき $\Dh$ の中では、手順1で $\Hp(\Dh, \Dh)$、つまり「$\Dh$ に $\Dh$ を入力したら停止するか」が計算されます。

すると、この計算でプログラム $\Dh$ の入力として $\Dh$ を与えた結果は、「停止する」か「停止しない」かのいずれかであることは間違いありません。つまり、「$\Hp(\Dh, \Dh)=\text{停止しない}$」か、または、「$\Hp(\Dh, \Dh)=\text{停止する}$」のいずれかです。

それぞれの場合を詳しく検討してみましょう。

ケース1： 「$\Hp(\Dh, \Dh)=\text{停止しない}$」と仮定

プログラム $\Dh$ 内で計算される関数 $\Hp(\Dh, \Dh)$ の値は仮定より「停止しない」になります。

$\Dh$ の動作によれば、$\Hp(\Dh, \Dh)=\text{停止しない}$ の場合、プログラム $\Dh$ は「何もせず停止する」ことになっています。

したがって、プログラム $\Dh$ の入力にプログラム $\Dh$ を与えた結果、プログラムは停止することになります。

これは、$\Hp(\Dh, \Dh)=\text{停止する}$ でなければならないことを示していますが、仮定「$\Hp(\Dh, \Dh)=\text{停止しない}$」と矛盾しています。

ケース2： 「$\Hp(\Dh, \Dh)=\text{停止する}$」と仮定

プログラム $\Dh$ 内で計算される関数 $\Hp(\Dh, \Dh)$ の値は仮定より「停止する」になります。

$\Dh$ の動作によれば、$\Hp(\Dh, \Dh)=\text{停止する}$ の場合、プログラム $\Dh$ は「無限ループにより停止しない」ことになっています。

したがって、プログラム $\Dh$ の入力にプログラム $\Dh$ を与えた結果は、停止しないことになります。

これは、仮定「$\Hp(\Dh, \Dh)=\text{停止する}$」に反して、実際には $\Hp(\Dh, \Dh)=\text{停止しない}$ でなければならないことになり、矛盾します。

2つの場合をまとめると、次の図のようになります。どちらの行でも、Halt の答え（①）と実際の結果（③）が食い違います。

図 4. $\Dh$ に $\Dh$ 自身を入力したときの2つの場合

結論

いずれの場合でも矛盾が生じるということは、そもそも関数 $\Hp$ を計算するアルゴリズム（プログラム）の存在を仮定したことが誤りだったということになります。段階2〜4は、段階1の仮定さえ認めればどれも正しく実行できる手順だったので、誤りの原因は段階1の仮定以外にありません。

よって、関数 $\Hp$ を計算するようなアルゴリズムは存在しないことが示せました。

注意

この定理が示しているのは、あくまでもいかなるプログラムとその入力の組に対しても停止性を判定をしてくれるようなプログラムは存在しないということです。入力として与えるプログラムと入力の組に何らかの制約を課せば停止性を証明することは可能です。実際に停止性が示せるプログラムは存在し、入力として与えられたプログラムの信頼性や安全性を示すツールとして用いられています。また、「停止する」「停止しない」に加えて「わからない」とも答えてよいことにすれば、多くのプログラムについて正しく判定する道具を作ることができます。定理が否定しているのは、「わからない」を使わずに、すべての場合に正しく答える判定器だけです。

【完全なバグ検出器やウイルス対策ソフトは作れない】

停止性問題が計算できないことは、「プログラムを調べる別のプログラム」全般に影を落とします。実は、プログラムの入出力としての振る舞いに関する性質のうち、自明でないもの（あるプログラムは満たし、別のあるプログラムは満たさない性質）は、すべて判定不可能であることが知られています（1953年に示されたライスの定理）。たとえば「このプログラムはどんな入力に対しても必ず停止するか」「このプログラムは決められた仕様どおりの関数を計算するか」を完全に当てる判定器は作れません。「2つのプログラムは同じ動作をするか」も、別の議論により判定不可能であることが知られています。

コンピューターウイルスの検出も同じです。1987年にフレッド・コーエンは、「与えられたプログラムがウイルスかどうかを完全に判定するプログラムは存在しない」ことを証明しました。証明の筋立ては停止性問題とそっくりで、もし完全な検出器 $D$ があったとして、「$D$ が『ウイルスでない』と判定したときだけ感染活動をするプログラム」を作ると矛盾が生じます。実際のウイルス対策ソフトが既知のパターン照合や経験則に頼らざるをえないのは、原理的に完璧な検出が不可能だからなのです。

この証明に煙に巻かれたような、なにか釈然としない気持ちを抱く人もいると思います。この定理により「コンピューターには計算できないことがある」ということを示したわけですが、このことは、コンピューターが非力だから導かれる結果ではないということには注意が必要です。コンピューターは、プログラム自身を自己言及的にデータとして与えることができるほど強力な記述能力や計算能力があることが、証明中で矛盾が発生した要因になっています。

計算不可能性は、ゲーデルの不完全性定理とも関係します。大まかには、自然数の基本的な計算を表せる十分に強い形式体系で、公理を機械的に列挙でき、矛盾がないなら、その体系だけでは証明も反証もできない命題が存在する、という定理です。「数学では何も証明できない」という意味ではありません。

Ruby, Julia, Python といったプログラミング言語も、メタプログラミングという自身の振る舞いを自身で書き換えることができる記述能力を備えています。

1.4. 対角線論法の視覚的理解

前節の証明で「対角線論法」という名前を使いましたが、なぜ「対角線」と呼ぶのでしょうか。この名前の由来を、表を使って説明します。

プログラムと入力の組み合わせ表

すべてのプログラムには番号をつけることができます（プログラムは有限長の文字列なので、辞書式順序などで番号付けが可能です）。これを $P_1, P_2, P_3, \ldots$ とします。同様に、すべての入力データにも番号をつけて $x_1, x_2, x_3, \ldots$ とします。

ここで、プログラム自身もデータとして扱えるので、入力としてもプログラム $P_1, P_2, P_3, \ldots$ を使うことにすれば、プログラムにプログラムを入力したときの停止性を、すべての組み合わせについて次のような表で表すことができます。

\(\Hp(P_i, P_j)\)	\(P_1\)	\(P_2\)	\(P_3\)	\(P_4\)	\(\cdots\)
\(P_1\)	\(\boxed{\text{停}}\)	停	不停	停	\(\cdots\)
\(P_2\)	不停	\(\boxed{\text{不停}}\)	停	停	\(\cdots\)
\(P_3\)	停	停	\(\boxed{\text{停}}\)	不停	\(\cdots\)
\(P_4\)	不停	停	不停	\(\boxed{\text{不停}}\)	\(\cdots\)
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\ddots\)

$\Hp(P_i, P_j)$

$P_1$

$P_2$

$P_3$

$P_4$

$\cdots$

$P_1$

$\boxed{\text{停}}$

停

不停

停

$\cdots$

$P_2$

不停

$\boxed{\text{不停}}$

停

$\cdots$

$P_3$

停

$\boxed{\text{停}}$

不停

$\cdots$

$P_4$

不停

停

不停

$\boxed{\text{不停}}$

$\cdots$

$\vdots$

$\ddots$

この表で、行はプログラム、列は入力を表しています。「停」は停止する、「不停」は停止しないの略です（表の値は説明のための例です）。たとえば、$P_2$ の行と $P_3$ の列が交わるセルには $\Hp(P_2, P_3)$ の値（プログラム $P_2$ に入力 $P_3$ を与えたときに停止するかどうか）が入ります。

対角線に注目する

表の対角線上のセル（左上から右下への斜め線上）には、$\Hp(P_1, P_1), \Hp(P_2, P_2), \Hp(P_3, P_3), \ldots$ という値が並んでいます。これは「プログラム $P_i$ に自分自身を入力として与えたときの停止性」を表しています。

$P_1$

$P_2$

$P_3$

$P_4$

$\cdots$

$P_1$

停

$P_2$

不停

$P_3$

停

$P_4$

不停

$\vdots$

$\ddots$

対角線を「反転」させた新しい行

ここで、証明で構築したプログラム $\Dh$ を思い出してください。$\Dh$ は次のように動作しました。

$\Hp(P, P) = \text{停止する}$ のとき → $\Dh$ は停止しない
$\Hp(P, P) = \text{停止しない}$ のとき → $\Dh$ は停止する

つまり、$\Dh$ は対角線上の各値を反転させた動作をします。

もし $\Dh$ が表のどこかの行 $P_k$ に対応するならば、$\Dh$ の行は次のようになるはずです。

	\(P_1\)	\(P_2\)	\(P_3\)	\(P_4\)	\(\cdots\)
\(\Dh\)	不停	停	不停	停	\(\cdots\)

$P_1$

$P_2$

$P_3$

$P_4$

$\cdots$

$\Dh$

不停

停

不停

停

$\cdots$

この行は、対角線上の値をすべて反転させたものです。

矛盾の発生

しかし、$\Dh$ もプログラムである以上、表のどこかの行に対応しているはずです。$\Dh = P_k$ だとしましょう。

すると、表の $k$ 行目と $k$ 列目が交わる対角線上のセル $\Hp(P_k, P_k) = \Hp(\Dh, \Dh)$ について考えます。

対角線上の元の値が「停」なら、$\Dh$ の定義により $\Dh$ は停止しないので「不停」
対角線上の元の値が「不停」なら、$\Dh$ の定義により $\Dh$ は停止するので「停」

いずれの場合も、$\Dh$ の行の対角線上のセルは、元の対角線の値と異なることになります。しかし、$\Dh = P_k$ ならば $\Hp(\Dh, \Dh) = \Hp(P_k, P_k)$ でなければならず、矛盾が生じます。

ここまでの流れを1枚の図にまとめると、以下のようになります。

図 5. 対角線論法のしくみ：対角線を反転した行はどの行とも一致できない

「対角線」の名前の由来

この証明が「対角線論法」と呼ばれるのは、表の対角線に注目し、その対角線上の値をすべて反転させた新しい行を構成することで矛盾を導くからです。

この手法は、数学者カントールが1891年の論文で、無限にも大きさの違いがあること（たとえば、実数全体は自然数全体より多く、すべての実数に自然数の番号を付けることはできないこと）を示すのに用いたもので、停止性問題の証明はその応用と見ることができます。

カントールの対角線論法との対応を整理します。

カントールの証明

停止性問題の証明

番号を付けた無限小数の一覧（1行に1つの実数）

番号を付けたプログラムの一覧（1行に1つのプログラム）

対角線上の各桁（k番目の数の小数第k位）

対角線上の値 $\Hp(P_k, P_k)$

各桁を別の数字に変えた新しい小数

対角線の値を反転した動作をする $\Dh$

新しい小数は一覧のどの行とも違う → 実数に番号を付け尽くすことはできない

$\Dh$ はプログラムなので一覧のどこかにあるはずなのに、どの行とも違う → 矛盾 → Halt は存在しない

結論の形が違う点に注意してください。カントールの証明では「一覧に載っていないものがある」ことが結論です。停止性問題の証明では、$\Dh$ が一覧に載っていないことはありえないので、$\Dh$ を作る材料になった Halt の存在が否定されます。

【止まるプログラムはどこまで粘れるか — ビジービーバー】

停止性問題が解けないことから、ふしぎな性質をもつ「計算できない関数」を作ることができます。その代表がビジービーバー関数 $\mathrm{BB}(n)$ です。これは、$n$ 個の状態と2種類のテープ記号（0と1）をもつチューリングマシンのうち、すべて0のテープから動かしていつかは必ず停止するものに限ったとき、停止するまでに動く最大ステップ数を表します。つまり「必ず止まるプログラムの中で、止まるまでにいちばん長く粘るものの記録」です。前に示したチューリングマシンの図の規則表は、2状態で6ステップ動いて止まる、この記録を持つマシンの1つです（練習問題で確かめます）。

小さな場合の値は $\mathrm{BB}(1)=1$、$\mathrm{BB}(2)=6$、$\mathrm{BB}(3)=21$、$\mathrm{BB}(4)=107$ です。$\mathrm{BB}(5)$ については、47,176,870ステップ動いて止まる5状態のマシンが1989年に見つかっていました。ところが、それが最長であること、つまり $\mathrm{BB}(5)=47{,}176{,}870$ の証明は、2024年にようやく完成しました。候補を発見するだけでなく、「それより長く動いて止まるマシンはない」とすべての候補について確かめる必要があるからです。世界中の参加者が協力したBusy Beaver Challengeでは、約1億8千万個の5状態マシンを調べ、その証明を証明支援ソフトCoq（現在の名称はRocq）で機械的に検証しました。状態がわずか5個でも、止まるかどうかを調べ尽くすのは大仕事なのです。

出典：Busy Beaver Challenge による発表（2024年7月2日）、Determination of the fifth Busy Beaver value（成果の論文）。ここでは停止状態を n 個に数えず、テープは初めすべて0、ヘッドは各ステップで左右いずれかへ1マス動く標準的な定義を使っています。

なぜ $\mathrm{BB}(n)$ は計算できないのでしょうか。もし計算できたとすると、$n$ 状態の任意のマシンを、すべて0のテープから $\mathrm{BB}(n)$ ステップだけ動かしてみて、まだ止まっていなければ「このマシンは永久に止まらない」と判定できてしまいます。任意のプログラムと入力の組は、「最初にテープへ入力を書き込んでから元の計算を始める」チューリングマシンに機械的に書き直せるので、これは停止性問題を解くことにほかなりません。つまり、停止性問題が解けない以上、$\mathrm{BB}(n)$ も計算できないのです。小さな表に収まりそうな素朴な関数が、原理的に求められないというのは不思議な話です。

2. ポストの対応問題

「停止性問題」は問題設定として不自然だという印象を持たれるかもしれません。この節ではより自然な形の計算不可能な問題である「ポストの対応問題」を紹介します。ポストの対応問題はどこにでもありそうなパズル問題です。アメリカの数学者エミール・ポスト（Emil Post）が1946年に発表したことから、この名前があります。

2.1. ポストの対応問題の定義と例

ポストの対応問題を例を使って説明します。

ポストの対応問題の例1

以下の3種類のドミノを1枚以上横にならべて、上の○と●の並びと下の○と●の並びがおなじになるような組合せをつくることができるか？（同じドミノを繰り返し用いてもよい）

図 6. 例1の3種類のドミノ

解答の考え方

まず、それぞれのドミノがどのような文字列を持っているかを確認します。

左のドミノ：上が「○」、下が「●○○」
中央のドミノ：上が「○●」、下が「○○」
右のドミノ：上が「●●○」、下が「●●」

これらのドミノを組み合わせて、上と下の文字列を同じにする必要があります。

解答

このパズル問題は、3種類のドミノを「右、中央、右、左」の順に配置すれば、上下とも「●●○○●●●○○」になっています。

図 7. 例1の解：右・中央・右・左の順に並べる

検証

上の並び：●●○ + ○● + ●●○ + ○ = ●●○○●●●○○
下の並び：●● + ○○ + ●● + ●○○ = ●●○○●●●○○

確かに同じ並びになっています。

では、次の問題はどうでしょうか。

ポストの対応問題の例2

以下の2種類のドミノを1枚以上横にならべて、上の○と●の並びと下の○と●の並びがおなじになるような組合せをつくることができるか？（同じドミノを繰り返し用いてもよい）

図 8. 例2の2種類のドミノ

解答の考え方

左のドミノ：上が「○」、下が「●○○」
右のドミノ：上が「○●」、下が「○○」

分析

この問題は、上下の○と●の数合わせがそもそもできません。

左側のドミノを1個使うと：上の長さが1、下の長さが3になる
右側のドミノを1個使うと：上の長さが2、下の長さが2になる

左側のドミノを使うと、使うたびに下の並びが2つずつ長くなってしまうため、上下の長さを合わせるには左側のドミノをまったく使えません。かといって、右側のドミノだけを並べると、上は「○●」のくり返し、下は「○○」のくり返しになり、両者が一致することはありません。

別の見方をすると、いちばん最初に置ける1枚は、上の並びと下の並びのどちらかが、もう一方の先頭部分になっていなければなりません。ところが、左のドミノは1文字目が○と●で食い違い、右のドミノは2文字目で○と●に分かれます。どちらも条件を満たさないので、そもそも先頭の1枚すら置けないことからも、解がないとわかります。

よって、同じ並びにはできないことがわかります。

2.2. ポストの対応問題の一般的な定義

この2つの例は、比較的簡単に答えが出せました。どのような（有限種類の）ドミノが与えられたとしても、そのドミノで上下の並びが同じにできるかどうかを判定する問題をポストの対応問題といいます。

ポストの対応問題

入力: 有限種類のドミノ。各ドミノの上と下には、記号（ここでは○と●）の並びが書かれている
問題: ドミノを1枚以上、横一列に並べて（同じ種類を何度使ってもよい）、上の並びと下の並びを同じにできるか
出力: Yes または No

ポストの対応問題では、ドミノを1枚以上並べます。0枚を許すと上下とも空文字列で常に一致し、問題になりません。

解が見つかったときに、それが本当に解であることは、上下の並びを1文字ずつ比べれば簡単に確かめられます。難しいのは、同じドミノを何枚でも使えるので、調べる並べ方に上限がないことです。

【ドミノの種類が少なければ解ける】

ドミノが2種類までの場合には、答えを必ず出すアルゴリズムがあることが1982年に示されています（例2はこの範囲の問題でした）。一方、5種類のドミノを使う問題に限っても判定するアルゴリズムは存在しないことが、2015年に示されました。3種類と4種類の場合は、まだわかっていません。

出典：T. Neary, Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words（2015年）。2種類の場合の結果（Ehrenfeucht, Karhumäki, Rozenberg, 1982年）もこの論文で紹介されています。

2.3. 停止性問題との関連

「ポストの対応問題」が解ければ「停止性問題」も解けるような巧妙な符号化が知られています。プログラム $P$ と入力 $x$ から、機械的な手順でドミノの組を作り、「$P$ が $x$ で停止する」ときに限って、そのドミノで上下の並びをそろえられるようにできるのです。

図 9. 停止性問題からポストの対応問題への還元

もしポストの対応問題を判定するプログラムがあれば、この変換と組み合わせて停止性問題が解けてしまいます。停止性問題は解けないので、「ポストの対応問題」も計算不可能です。つまり、停止性問題からの還元により決定不能であることが示されます。

これは「停止性問題」を「ポストの対応問題」のためのアルゴリズムを用いて解けるように帰着させたということになります。このように、ある問題を別の問題に帰着させることを還元といいます（この例では「停止性問題」を「ポストの対応問題」に還元した）。還元の向きに注意してください。解けないとわかっている問題（停止性問題）を、調べたい問題（ポストの対応問題）に還元することで、調べたい問題も解けないことがわかります。還元については次章でもう少し詳しく説明します。

2.4. 半決定性について

「ポストの対応問題」も、答えがあるときに Yes、ないときに No を出力する問題とみると、決定問題と考えることができます。「停止性問題」にも「ポストの対応問題」にも、答えが Yes なら、いつか必ず Yes と答えて止まる手続きがあります。

停止性問題：$P$ を入力 $x$ で実際に動かしてみて、止まったら「停止する」と答える。
ポストの対応問題：ドミノを1枚並べる並べ方をすべて試し、次に2枚、3枚、…と枚数を増やしながら試して、上下がそろう並べ方が見つかったら Yes と答える。枚数ごとの並べ方は有限通りなので、解があればいつか必ず見つかる。

しかし、答えが No のときには、これらの手続きは永久に止まりません。明らかに止まらないとわかる簡単な場合を見分ける工夫は加えられますが、それでもすべての No の入力で止まるようにはできません。止まらない手続きを外から見ていても、まだ止まっていないだけなのか、永久に止まらないのかを見分けることはできません。

このように、「答えが Yes である場合にはいつかは止まって正しく答え、No のときには止まらなくてもよい」という手続きが存在する性質を「半決定的」（半決定可能）であるといいます。停止性問題とポストの対応問題は、半決定的ではあるけれども、No のときも必ず止まって答える手続き（アルゴリズム）は存在しない問題です。

もし No の側にも「No ならいつか必ず No と答えて止まる手続き」があれば、Yes 用と No 用の2つの手続きを1ステップずつ交互に進めることで、いつかはどちらかが止まり、答えが必ず決まります。これは問題が解けることを意味します。停止性問題は解けないので、「停止しない」ことを必ずいつか言い当てる手続きは存在しないのです。

この「いつか」というのは1秒後かもしれませんし、100億年後かもしれないのが厄介なところです。答えが Yes の場合でも、止まるまでにかかる時間の上限を前もって知る方法はありません（もし知ることができれば、ビジービーバーの節で見たように、その時間だけ待てば停止性問題が解けてしまいます）。半決定的な手続きは、待っても答えが出ないうちは何も結論できないので、実際に使う道具としては限界があります。

3. まとめ

この章では、以下の重要な概念を学びました。

停止性問題：任意のプログラムが停止するかどうかを判定する問題
チューリングマシン：テープ・ヘッド・状態・規則表だけからなる、計算のいちばん単純なモデル
計算不可能性：停止性問題を解くアルゴリズムは存在しないことの証明（背理法と天邪鬼プログラム）
対角線論法：表の対角線上の値を反転させることで矛盾を導く証明手法
ポストの対応問題：より自然な形の計算不可能な問題
還元：ある問題を別の問題に帰着させる手法
半決定性：Yes の場合は必ず止まって判定できるが、No の場合は止まらないこともある性質

次章では、視点を「計算できるかどうか」から「どれくらい難しいか」へ移し、問題の難しさをコンピューター科学がどう扱うのかを考えます。

4. 練習問題

基本の確認から始め、手を動かして解く問題、証明のしくみを考える問題の順に並べています。解答は、自分で考えてから開いてください。

問題1: プログラム $P_2$ の停止性

本文中のプログラム $P_2$ について、次の入力に対する停止性関数 $\Hp(P_2, n)$ の値をそれぞれ答えよ。停止する場合は、出力される値も答えよ。

$n=3$
$n=0$
$n=15$

解答

$\Hp(P_2, 3)=\text{停止する}$。$x$ の値は $0 \rightarrow 3 \rightarrow 6 \rightarrow 9 \rightarrow 12$ と変化し、$10$ 以上になった時点で $12$ を出力して停止します。
$\Hp(P_2, 0)=\text{停止しない}$。$x$ の値は $0$ のまま変わらず、$x<10$ が成り立ち続けるため、永久に繰り返しが続きます。
$\Hp(P_2, 15)=\text{停止する}$。1回目の加算で $x=15\geq 10$ となるので、$15$ を出力して停止します。

2行目の加算は、3行目の比較より先に必ず1回実行されます。そのため (3) では、比較の前に $x$ が $15$ になっている点に注意してください。

問題2: 定理からいえること

停止性問題が計算不可能である（本文の定理）ことからいえることとして、正しいものをすべて選べ。

どのようなプログラムについても、それが停止するかどうかを判定することは決してできない
プログラムの範囲を限定すれば、停止性を判定できる場合がある
どんなに高速なコンピューターを開発しても、停止性問題を解くプログラムは作れない
停止性問題は、計算に時間がかかりすぎるため、事実上解けない問題である

解答

正しいのは (2) と (3) です。

(1) は誤りです。定理が主張しているのは「あらゆるプログラムと入力の組に対して停止性を判定する1つのアルゴリズムは存在しない」ということです。個々のプログラムについては、停止性が証明できる場合があります（$P_1$ や $P_2$ がその例でした）。
(2) は正しいです。本文の「注意」で述べたとおり、プログラムに制約を課せば停止性を証明できる場合があり、実際にそのようなツールも存在します。
(3) は正しいです。計算不可能性は計算モデルの原理的な限界であり、計算速度の問題ではありません。
(4) は誤りです。「時間がかかる」のではなく、原理的にアルゴリズムが存在しないのです。時間の問題であれば、次章で扱う計算量の話になります。

問題3: チューリングマシンを動かす

本文の「チューリングマシンの部品と1ステップの動き」の図にある規則表（2状態の例）のチューリングマシンを、すべて0のテープで、状態 A から動かす。停止するまでに何ステップかかるか。また、停止したときテープに1はいくつ書かれているか。

解答

6ステップで停止し、テープには4個の1が残ります。

最初のヘッドの位置を0番のマスとし、そこから右を正、左を負の番号で表します。各ステップの後のテープの様子を、ヘッドの位置を [ ] で囲んで示します（表示していないマスはすべて0）。

ステップ	状態	読んだ記号	書く記号・動く向き	次の状態	テープ（−2〜+1番のマス）
1	A	0	1・右	B	0 0 1 [0]
2	B	0	1・左	A	0 0 [1] 1
3	A	1	1・左	B	0 [0] 1 1
4	B	0	1・左	A	[0] 1 1 1
5	A	0	1・右	B	1 [1] 1 1
6	B	1	1・右	停止	1 1 [1] 1

ステップ

状態

読んだ記号

書く記号・動く向き

次の状態

テープ（−2〜+1番のマス）

1・右

0 0 1 [0]

1・左

0 0 [1] 1

1・左

0 [0] 1 1

1・左

[0] 1 1 1

1・右

1 [1] 1 1

1・右

停止

1 1 [1] 1

本文の図のテープは、ステップ2の後の様子（状態 A、ヘッドの下が1、その右隣も1）にあたります。

$\mathrm{BB}(2)=6$ なので、これは2状態のマシンのなかで最も長く動いて止まるものの1つです。状態が2個だけでも、同じマスを何度も行き来しながら動くことがわかります。

問題4: ポストの対応問題を解く

次の3種類のドミノ A、B、C を使うポストの対応問題を考える。上下の並びをそろえる並べ方を1つ見つけよ（同じドミノを何度使ってもよい）。

図 10. 問題4のドミノ

A は上「●」下「●●」、B は上「○○●」下「○」、C は上「●●」下「●○」です。

ヒント：左端に置けるのは、上下の並びの一方が、もう一方の先頭部分になっているドミノだけです。

解答

A、C、B、A の順に並べると、上下とも「●●●○○●●」になります。

上の並び：● + ●● + ○○● + ● = ●●●○○●●
下の並び：●● + ●○ + ○ + ●● = ●●●○○●●

考え方：左端に置けるのは A（上「●」は下「●●」の先頭部分）と B（下「○」は上「○○●」の先頭部分）です。C は2文字目で●と○に分かれるので置けません。

A から始めると、下が「●」だけ先に進みます。次のドミノは、上がこの「●」で始まる必要があるので A か C です。C を置くと上「●●●」、下「●●●○」となり、下が「○」だけ先に進みます。次は上が○で始まる B を置くと、上「●●●○○●」、下「●●●○○」となり、今度は上が「●」だけ先に進みます。最後に、下が●で始まり、上下の差を埋める A を置くと、上下がそろいます。

なお、計算機で全探索すると、8枚以下の並べ方で解になるのはこの1通りだけです（解を2回繰り返した8枚の並びは除きます）。B から始める並べ方は、調べた範囲では上が先に進んだ状態が解消せず、解になりませんでした。

問題5: 解がないことを示す

次の3種類のドミノ A、B、C を使うポストの対応問題の答えは No である（上下をそろえる並べ方はない）。その理由を説明せよ。

図 11. 問題5のドミノ

A は上「○●」下「○」、B は上「●」下「●○○」、C は上「○」下「○○」です。

ヒント：本文の例2と違い、A も B も C も左端に置けます。そこで、●の個数と、並びの長さに注目してみましょう。

解答

A、B、C をそれぞれ $a, b, c$ 枚使ったとします。

●の個数：上の●は A と B に1個ずつあるので $a+b$ 個、下の●は B に1個あるだけなので $b$ 個です。上下がそろうには個数が等しい必要があるので $a=0$、つまり A は使えません。
並びの長さ：A を使わないとき、上の長さは $b+c$、下の長さは $3b+2c$ です。等しくなるのは $b=c=0$ のときだけです。

結局、ドミノを1枚も使わない場合しか残りません。ポストの対応問題ではドミノを1枚以上並べる決まりなので、答えは No です。

このように、並び方を調べなくても、個数や長さのような「並べ方によらない量」で解がないと示せることがあります。ただし、どんなドミノの組にも使える、このような判定方法は存在しません（それが本文の結論です）。

問題6: 対角線論法を適用する

4つのプログラム $P_1,\ldots,P_4$ について、$\Hp(P_i,P_j)$ の値が次の表のようになっていたとする（停＝停止する、不停＝停止しない）。

\(\Hp(P_i, P_j)\)	\(P_1\)	\(P_2\)	\(P_3\)	\(P_4\)
\(P_1\)	不停	停	停	不停
\(P_2\)	停	停	不停	不停
\(P_3\)	停	不停	不停	停
\(P_4\)	不停	停	停	停

$\Hp(P_i, P_j)$

$P_1$

$P_2$

$P_3$

$P_4$

$P_1$

不停

停

不停

$P_2$

停

不停

$P_3$

停

不停

停

$P_4$

不停

停

天邪鬼プログラム $\Dh$ に入力 $P_1,\ldots,P_4$ を与えたときの停止性を、それぞれ答えよ。
$\Dh$ の行は、$P_1,\ldots,P_4$ のどの行とも一致しないことを、それぞれ食い違う列を指摘して確かめよ。

解答

対角線は $\Hp(P_1,P_1)=$不停、$\Hp(P_2,P_2)=$停、$\Hp(P_3,P_3)=$不停、$\Hp(P_4,P_4)=$停です。$\Dh$ はこれを反転するので、入力 $P_1,P_2,P_3,P_4$ に対して順に停、不停、停、不停となります。
$P_1$ の行とは1列目（$P_1$ は不停、$\Dh$ は停）、$P_2$ の行とは2列目（停と不停）、$P_3$ の行とは3列目（不停と停）、$P_4$ の行とは4列目（停と不停）で食い違います。

ほかの列でたまたま食い違うこともあります（たとえば $P_1$ の行とは2列目も食い違います）。しかし、どんな表であってもk行目とはk列目で必ず食い違うことが保証されている点が大切です。表の値を知らなくても、この保証だけで $\Dh$ がどの行とも一致しないと言えます。

問題7: 天邪鬼でないプログラムでは矛盾が起きない

本文の天邪鬼プログラム $\Dh$ の代わりに、Halt の答えに素直に従う次のプログラム $Q$ を考える。

$\Hp(P,P)=\text{停止する}$ なら、ただちに停止する
$\Hp(P,P)=\text{停止しない}$ なら、無限ループに入る

$Q$ に $Q$ 自身を入力として与えたとき、本文と同じように場合分けをしても矛盾は生じないことを確かめよ。また、このことから、本文の証明で $\Dh$ の何が重要だったかを説明せよ。

解答

$\Hp(Q,Q)=\text{停止する}$ と仮定すると、$Q$ はただちに停止します。実際に停止するので、Halt の答えは正しく、矛盾しません。
$\Hp(Q,Q)=\text{停止しない}$ と仮定すると、$Q$ は無限ループに入ります。実際に停止しないので、この場合も Halt の答えは正しく、矛盾しません。

どちらの場合も矛盾しないので、$Q$ からは何も結論できません。本文の証明で重要だったのは、$\Dh$ が Halt の答えと逆の動作をすることです。そのため、$\Dh$ 自身について Halt がどちらを答えても、実際の動作がその答えを裏切ることになりました。「自分自身を入力する」だけでは矛盾は生じず、「答えを反転する」ことと組み合わせてはじめて矛盾が生じます。対角線論法で、対角線の値を反転した行を作ったのと同じです。

問題8: 半決定性

停止性問題は「半決定的」である。つまり、$\Hp(P,x)=\text{停止する}$ の場合に限れば、いつかは必ず「停止する」と正しく出力して停止する方法が存在する。その方法を簡潔に説明せよ。また、ポストの対応問題について、答えが Yes の場合にいつか必ず Yes と出力して停止する方法を説明せよ。

解答

停止性問題：プログラム $P$ に入力 $x$ を与えて、実際に実行（シミュレート）します。$P$ が停止したら「停止する」と出力して停止します。$P$ が停止する場合は、有限時間でこの手続きも「停止する」と正しく出力します。一方、$P$ が停止しない場合は、この手続きも永久に答えを出せませんが、半決定性の要件としてはそれで構いません。

ポストの対応問題：並べるドミノの枚数を1枚、2枚、3枚、…と増やしながら、その枚数のすべての並べ方を順に調べ、上下がそろうものが見つかったら Yes と出力して停止します。ドミノの種類が $m$ 種類なら、$k$ 枚の並べ方は $m^k$ 通りで有限なので、各枚数の調査は必ず終わります。解が $k$ 枚でできるなら、$k$ 枚目の調査までに必ず見つかります。

誤答しやすい点：「枚数の少ない順に調べる」代わりに「1種類のドミノだけを1枚、2枚、3枚、…と並べる並べ方を先に調べ尽くす」ようにすると、その調査が終わらず、ほかの並べ方にたどり着けません。有限通りずつ区切って調べることが大切です。

← 目次へ戻る