チューリング認識不可能な言語と対角線論法

概要
判定不可能な言語
- 証明
- 証明
対角線論法
- 証明
参考資料

概要

今回は以下に示す言語が判定不可能であり、その補集合が認識不可能であることを示していきます。

$A_{TM} = \{\langle M, w\rangle | M はチューリング機械で w を受理する\}$

その次に、証明に関連して対角線論法について説明します。

判定不可能な言語

上記の $A_{TM}$ が判定不可能なことは以下のような手順で示せます。

証明

以下のような挙動をする TM $H$ を考える。この $H$ が実際には存在しないことを示せれば $A_{TM}$ が判定不可能であると示せる。

$H(\langle M, w\rangle) = 受理（M が w を受理する時）$
$H(\langle M, w\rangle) = 拒否（M が w を受理しない時）$

この $H$ を用いる TM $D$ を考える。 $D$ は TM $M$ のコード化 $\langle M \rangle$ を入力として、 $H$ に対して $\langle M, \langle M\rangle\rangle$ を走らせる。そうして得られた出力の逆を $D$ は出力する。つまり、 $D$ の挙動は以下のようになる。

$D(\langle M\rangle) = 受理（M が \langle M\rangle を受理しない時）$
$D(\langle M\rangle) = 拒否（M が \langle M\rangle を受理する時）$

その時の挙動を記述すると

$D(\langle M\rangle) = 受理（D が \langle D\rangle を受理しない時）$
$D(\langle M\rangle) = 拒否（D が \langle D\rangle を受理する時）$

つまり $D(\langle D\rangle)$ が受理でもあり拒否でもあることとなり、矛盾する

対角線論法を用いてこの定理は証明されていますが、それについては後述します。

さて、 $A_{TM}$ が判定不可能であることが示されました。次に、以下の定理を示します。

任意の言語に対し、言語とその補集合がどちらも Turing 認識可能であるときに限り、その言語は判定可能である。

これが示せると、対偶を取ることにより

言語 $A$ が判定不可能で認識可能 $\Rightarrow A^C$ （ $A^C$ は $A$ の補集合）が認識不可能

であることが示せます。

証明

示すべきことは二つあります。

言語が判定可能なら、その言語と補集合はどちらも認識可能
言語とその補集合がどちらも認識可能なら、その言語は判定可能

1 は明らかです（判定の方が認識より厳しい条件です）。

2 を示します。言語 $A$ を認識する TM を $M_1$ 、 $A^C$ を認識する TM を $M_2$ とします。これらを使用して以下の挙動をする 2 テープ TM $M$ を考えます。

$M$ は入力 $w$ に対して

並列に $M_1$ と $M_2$ の両方を動作させる。
$M_1$ が受理するならば $M$ は $w$ を受理し、 $M_2$ が受理するならば拒否する。

$M_1$ と $M_2$ のどちらか一方は必ず $w$ を受理し、受理の定義からそれは有限時間内に起こるので $M$ は必ず停止します。 $w\in A$ であれば $M$ は受理し、それ以外は拒否するので $M$ は $A$ に対する判定装置となっています。よって、 $A$ が判定可能なことが示せました。

以上の証明により、（ $A_{TM}$ が Turing 認識可能なので） $A_{TM}^{C}$ が Turing 認識不可能な言語であることが示せました。

対角線論法

対角線論法の話に入る前に、写像について簡単に復習しておきます。

$A, B$ を集合とした時、任意の $A$ の要素 $a$ に対し、それに対応する $B$ の要素 $f(a)$ をただ一つ対応付けることを考えます。このとき、 $f$ のことを $A$ から $B$ への写像と言います。また、写像の全射及び単射については以下のように定義されます。

$a, a'\in A,\ f(a)=f(a') \Rightarrow a = a'$ が常に成り立つとき、 $f$ は単射であるという。
任意の $b\in B$ に対し、 $a\in A$ が存在し、 $b = f(a)$ となるとき、 $f$ は全射であるという。

よって、以下のことが言えます。

$f: A \to B$ を写像とする。

$f$ が全射 $\Rightarrow$ $A$ の大きさは $B$ 以上
$f$ が単射 $\Rightarrow$ $B$ の大きさは $A$ 以上

「大きさ」というかなり怪しい表現をしましたが、有限集合に限定すればここでいう大きさとは集合内の要素の個数を指しています（無限集合に関しては濃度という概念を適宜参照してください）。

さて、対角線論法は一般的な背理法のテクニックとして知られています。具体例の一つとして無限集合同士の大きさの比較に役立ちます。以下、簡単に集合 $X$ と冪集合 $2^X$ の大きさが異なることを示します。大きさが異なることを示すのには、いかなる写像 $\psi$ によっても $2^X$ のある要素に飛ぶような $X$ の要素が取れないことを言えば良いです。厳密に書き下すと以下のようになります。

$\psi: X\to 2^X を写像、Y=\{x\in X|x\notin\psi(x)\} とするとき、\psi(x)=Yとなるx\in X は存在しない$

証明

背理法により示す。 $\psi(x)=Y$ となるような $x\in X$ の存在を仮定する。

$x\in Y$ とすると仮定より $x\in \psi(x)$ でもあるが、これは $Y$ の定義に矛盾する。 $x\notin Y$ とすると $x\notin \psi(x)$ でもあるが、これも $Y$ の定義に矛盾する。よって示された。

集合の大きさを比べる時に、写像 $\phi$ の全射性、単射性を使うことは非常によくあります。これをもっと対角線っぽくした具体例が $\mathbb{R}$ が非可算であることの証明です。 $\mathbb{N}\to\mathbb{R}$ となる全単射の写像が作れないということを、小数点以下の各桁で $n=1, n=2,\dots$ と異なるものを取ってくることで示しています（この辺は画像で見た方が分かりやすいですが）。

高校数学の美しい物語というサイトではより直接的に上記の定理を行列を用いて言い換えています。

カントールの定理の証明と対角線論法 | 高校数学の美しい物語

（こういうのって勝手に貼っていいものなんでしょうか）

$\Sigma$ 上の TM は可算個であり、 $\Sigma$ 上の言語全体の集合 $2^{\Sigma^*}$ が非可算個、各 TM に対してそれが認識する言語を対応させる写像 $L$ が単射であることを考えると、チューリング認識不可能な言語が存在すること自体は直感的に理解できるかと思います（詳細に証明しようと思ったら、 $\mathbb{R}$ が非可算であることの証明から書くことになると思います）。