こんにちはkoheです。今回は 数えられ(ない)る集合の話と無限ループが起きることを判定できるか？という話をしていきたいと思います。

みなさんは全ての数は数えられると思いますか？無限ループが起きるかどうかを判定できると思いますか？

カントールの対角線論法

カントールの対角線論法とは？

カントールの対角線論法は、「実数は自然数によって数え上げられない（不可算である）」ことを証明するための有名な方法です。

対角線論法

0以上1以下の実数を列挙してみる

「すべての実数をリストアップした」と主張する人がいたとしましょう。特に、0以上1以下のすべての実数を小数展開で書いたリストを考えます。たとえば、次のように並べたとします（実際は無限に続くと想定）

ここで、「このリストには0以上1以下のすべての実数が含まれている」と仮定してみます。

対角線上の数字を1つずつ見て新しい数を作る

1. 上の表を縦横に眺めて、1番目の小数の1桁目、2番目の小数の2桁目、3番目の小数の3桁目…というふうに対角線上の数字を取り出す。
2. 取り出した数字を1桁ずつ変える（例: 0→1、1→2 など、一律に1を足して10なら0に戻す）。

• 1 -> 2
• 9 -> 0
• 4 -> 5
• 0 -> 1
• 0 -> 1

対角線の数字を変えた結果、次のような数が得られるとします。

0.20511...

この数は、元のリストの1番目の数とも2番目の数とも…n番目の数とも決して一致しません。なぜなら、1番目の数とは小数第1桁が異なり、2番目の数とは小数第2桁が異なり…という具合で、必ずどこかで違いが出るからです。

矛盾の発生

「リストには0以上1以下の実数がすべて入っている」としたのに、リストには存在しない実数（0.20511...）を作れてしまいました。これは矛盾です。よって、0以上1以下の実数を自然数で完全に列挙することはできない、というわけです。
この方法がカントールの対角線論法です。

ポイント

• 可算集合：要素を「1番目、2番目、3番目…」と番号付け（自然数と一対一対応）ができる集合のこと。例：自然数の集合、整数の集合、有理数の集合など。
• 不可算集合：上記のような「番号付け」で網羅できない集合。例：実数の集合。

停止性問題とは？

停止性問題（Halting Problem）とは、

「任意のプログラム Pと入力 I が与えられたときに、P は有限時間で停止するか？」

>計算可能性理論において停止性問題（ていしせいもんだい、英: halting problem）または停止問題は、「どんなチューリングマシン^{[注 1]}、あるいは同様な計算機構についても、それが有限時間で停止するかを判定できるアルゴリズム」は可能か、という問題。

停止性問題 - Wikipedia

ウィキメディア財団ウィキメディアプロジェクトへの貢献者

全プログラムを表に並べる――仮定から始める

プログラム（チューリングマシン）は理論的には有限文字列で表せるため、全プログラムを列挙できます。
たとえば M1,M2,M3,…と書くことができます。

これらのプログラムについて、「プログラムMi が入力 j で停止するかどうか」を次のような表で表してみましょう。

※無限ループするかどうかを判定する。

ここで「?」は本来「停止／停止しない」を示すはずのマス目ですが、一旦は「未知」としておきます。

「停止を判定するプログラム」があると仮定

「すべてのプログラムと入力の組み合わせについて、停止か否かを誤りなく判定できるプログラム（＝停止判定プログラム）がある」と仮定してみましょう。
もしそれが可能なら、この表の各マスを「停止(1)」または「停止しない(0)」で完璧に埋められるはずです。

図示イメージ（本当は無限大の表ですが、一部だけ）:

• ここで「1」と書いたら「その行のプログラムは、その列の入力を与えたら停止する」ことを意味し、「0」と書いたら「停止しない」ことを意味する、とします。

対角線論法

対角線上の要素を見ていく

まずは下記のように、対角線上の位置（行と列の番号が同じところ）だけに注目します。

ここで T[i,i]は「プログラム Mi​ が入力 i で停止するかどうか」を表す値（1か0）です。

新プログラムを定義

この対角線上の情報を利用して、新たなプログラム D を次のように定義します。

D は入力 n を受け取ると:

1. Mₙ（= 列挙表の n 番目のプログラム）を、入力 n でシミュレートする。

2. もし Mₙ(n) が 停止する(=1) と判断したら、D は 停止しない（無限ループ）。

3. もし Mₙ(n) が 停止しない(=0) と判断したら、D は 即座に停止 する。

このように、
「もし相手(= Mₙ)が止まるなら自分は止まらない。止まらないなら自分は止まる」
という風に、対角線要素を反転した振る舞いをプログラム D で実装します。

こうするとこのDは表の中に存在せず、全てのプログラムを列挙しているはずなのに矛盾が生じます。これは無限ループを判定できるという仮定がまちがっていたこととなり、無限ループがおきるかどうかの判定はできないということになります。

具体例

対角線上の要素を確認する

この表の 対角線上の要素（M₁の入力1、M₂の入力2、M₃の入力3、M₄の入力4…）を抽出します。

対角線上の数字は次の通りです。

• M₁(1) = 1
• M₂(2) = 1
• M₃(3) = 1
• M₄(4) = 0
  ...

対角線上の数字を変える

対角線の各数字を以下のように反転します。
ルール:

• 1 -> 0（停止 -> 停止しない）
• 0 -> 1（停止しない -> 停止）

よってプログラムDは

• D(1) = 0
• D(2) = 0
• D(3) = 0
• D(4) = 1
• ...

となり、この表には存在しないことになる。

ぜひ皆さんもプログラムが無限ループをするかどうかを一般的に判定できるか迷ったらこのことを思い出してください。