第 5 回 停止問題

本日の内容

• 5-1. 宿題の解答
• 5-2. 濃度
• 5-3. 停止問題
• 5-4. 帰納的集合、帰納的可算集合
• 5-5. 次週の予告

今回は対角線論法を用いて停止問題の計算不能性を証明します。まず、対角線 論法を分かりやすく説明するため、集合論の濃度と言う概念を紹介 します。

5-1. 宿題の解答

Turing 機械のコードを素数巾の積で表さずに、単純に区切り記号で区切る用 にします。 すると、特定のδ関数の値の検索を Turing 機械のコードの長さに比例した時 間でできるようになります。

5-2. 濃度

集合 $A$ , $B$ に対して、 $A\le B$ を 「 $A$ から, $B$ への 1-1 関数が定義できること」と定めます。 $A\le B$ かつ $B\le A$ のとき $A\equiv B$ と表し、 $A\le B$ かつ $B\le A$ でないとき $A<B$ と表すことにします。

例5-1

$\left\{0,1\right\}<\left\{0,1,2\right\}$

証明(1) $\left\{0,1\right\}\le \left\{0,1,2\right\}$

$f\left(0\right)=0$ , $f\left(1\right)=1$ と関数 $f$ を定義すると条件を満たします。

(2) $\left\{0,1,2\right\}\le \left\{0,1\right\}$ でないこと

条件を満たす関数 $g$ が存在したとします。 すると、 $g\left(0\right)=x$ , $g\left(1\right)=y$ の値 x, y に関して、 $x\ne y$ とならなければならないので $x=0,y=1$ または $x=1,y=0$ が成り立つ必要があります。 しかしそれでは $g\left(2\right)$ の値を 1-1 に定めることができなくなり、 $g$ が存在することに矛盾します。

例5-2

自然数≡偶数

証明(1)自然数≦偶数

f(x)= 2 x とすることにより、 自然数の各要素を偶数の要素へ 1-1 に対応付けられます。

(2)偶数≦自然数

g(x)= x/2 とすることにより、 偶数の各要素を自然数の要素へ 1-1 に対応付けられます。

演習5-1

自然数≡整数 を証明しなさい

演習5-2

自然数≡有理数 を証明しなさい

対角線論法

自然数 < 0以上1未満の実数

証明(1)自然数 ≦ 0以上1未満の実数

次のような対応を考えます。

このようにすると、任意の自然数を 0 以上 1 未満の実数に 1-1 で対応付け ることができます。

(2)0以上1未満の実数 ≦ 自然数 でない

0 以上 1 未満の実数を自然数に対応付ける関数が存在したとして矛盾を導き ます。

そのような関数が存在したとします。 簡単のため、全射だと仮定します(全射でない場合も容易に証明を変更するこ とができます)。 すると、 1 に対応付けられた実数、 2 に対応付けられた実数、 3 に対応付けられた実数と順に並べることができます。 例えば次のように並べることができたと仮定しましょう。

この時、 0.6706… と、各桁の数を (9-対角線上の数) となるように並べた実数を考えることができます。 しかし、このように定義した数は上の並びのどこにも現れることはできません。 なぜなら、もし、n番目に並べようとすると n 桁目の 値が食い違ってしまうからです。 したがって、自然数に対応付けることができない実数が存在することになるの で仮定に矛盾します。

註

1=0.9999… と実数は二通りの表し方があるので、これを考慮しないと厳密な 証明にはなりません。

演習5-3

自然数 < 実数 を示しなさい。

演習5-4

上記の証明の不備を取り除くにはどうすれば良いですか？

巾集合の濃度

集合 $A$ に対して、その部分集合全体の集合を A の 巾集合 と呼び、 $2^A$ 、 $P\left(A\right)$ 、 $Pow\left(A\right)$ などと書きます。 式で集合を定義すると $2^A=\left\{x|x\subseteq A\right\}$ となります。 例えば、 $\left\{\mathrm{a},\mathrm{b}\right\}$ の巾集合は $2^{\left\{\mathrm{a},\mathrm{b}\right\}}=\left\{\mathrm{\phi },\left\{\mathrm{a}\right\},\left\{\mathrm{b}\right\},\left\{\mathrm{a},\mathrm{b}\right\}\right\}$ となります( $\mathrm{\phi }$ は空集合)。

有限集合の要素数を n とします。一つの部分集合に各要素が含ま れるか含まれないかを 1, 0 で表すと、 n 桁の二進数で一つの部分 集合を定めることができます。

従って、要素数 n の有限集合の巾集合の要素数は $2^n$ になります。

定理

$A<2^A$

証明(1) $A\le 2^A$

$2^A$ には $A$ のすべての部分集合が含まれています。 $A$ の要素 $x$ に対して $x$ だけからなる部分集合 $\left\{x\right\}$ は必ず $2^A$ に含まれます。 よって、 $f\left(x\right)=\left\{x\right\}$ とすれば、すべての $A$ の要素に対して 1-1 になります。

(2) $2^A\le A$ でない

$g:2^A\to A\text{(1-1)}$ なる関数が存在すると仮定して、矛盾を導きます。

このような関数の存在を仮定して、次の集合を考えます。

そして、 $g\left(X\right)$ の値を $z$ とします。 ここで、 $z$ が $X$ に含まれるか否かを議論します。

1. $z$ が $X$ に含まれるとします。 すると、 $X$ の定義により $z=g\left(X\right)$ は $X$ に含まれないということになり、矛盾します。
2. $z$ が $X$ に含まれないとします。 すると、 $X$ の定義により、逆に $z=g\left(X\right)$ は $X$ に含まれることになり、これも矛盾します。

したがって、 $z$ は $X$ に含まれても、含まれなくても矛盾するので、仮定が矛盾していることになり ます。

計算できない関数の存在

集合 $A$ に対して、ある要素 $x$ が含まれるとき 1、含まれない時 0 となる関数を特性関数といい、 ${\chi }_A\left(x\right)$ で表します。

自然数全体の集合を $\mathrm{N}$ で表すことにします。 すると自然数の部分集合全体は $2^{\mathrm{N}}$ で表せます。 自然数の部分集合に対する特性関数の集合全体を考えると、 $2^{\mathrm{N}}$ と同じ濃度になります。

前回示した通り、 Turing 機械のコードは自然数で表され、自然数とは 1-1 onto の関係にあります。 従って、Turing 機械のコード全体の濃度は自然数と等しくなります。 従って、 $\mathrm{N}<2^{\mathrm{N}}$ より、 Turing 機械のコードに対応しない自然数の部分集合の特性関数が存在するこ とになります。

5-3. 停止問題

さて、具体的に Turing 機械が存在しないような関数を紹介します。 次のような関数 $f$ は計算できません。

$f\left(x,y\right)=1$

もし、コード x の Turing 機械に入力 y を入れた時、計算が停止し、 何らかの出力が出る。

$f\left(x,y\right)=0$

もし、コード x の Turing 機械に入力 y を入れた時、計算が停止しな い。

この問題を停止問題と言います。

証明

上記の $f$ が存在するとして矛盾を導きます。

$f$ が Turing 機械で計算できるとすると、 Church の提唱により、 次のような 1 入力のTuring 機械 $M$ を作ることができます。

1. もし、コード x の Turing 機械に入力 x を入 れた時、計算が停止し、何らかの出力が出る場合は、無限ループに入る。
2. 一方、もし、コード x の Turing 機械に入力 x を入 れた時、計算が停止しないことが分かれば 0 を出力する。

これが Turing 機械で計算できるので、この Turing 機械のコードを z と置くことができます。 そこで、 $f\left(z,z\right)$ を考えます。 もし、 この値が 1 だとすると、コード z の Turing 機械に入力 z を入れると停止することが分かります。 しかし、これは $M$ に入力 z を与えることになります。 これが停止するということは 0 を出力、つまりコード z の Turing 機械に z を入れた時停止しないことになり、矛盾します。

一方、 $f\left(z,z\right)$ が 0 だとします。つまり コード z の Turing 機械に z を入力した時停止しないと判断されたとします。 すると、 $M$ の定義によりこれはコード z の Turing 機械に z を入力した時、停止すると 判断して無限ループに入ったと考えることができますが、これも矛盾していま す。 よって、 $f$ が存在するという仮定が矛盾していることになります。

5-4. 帰納的集合、帰納的可算集合

特性関数を計算する Turing 機械が存在するようが集合を 帰納的集合 と言います。 また、Turing 機械で全ての要素を次々と書き出すことができる(任意の要 素は十分長い時間あれば必ず出力される)集合を帰納的可算集合と 言います。

演習5-5

帰納的集合は帰納的可算集合であることを示しなさい。

演習5-6

ある集合と、その補集合がともに帰納的可算集合であるなら、その集合が帰納 的集合であることを示しなさい。

5-5. 次週の予告

線形加速定理を説明します。