第 1 回 計算可能性理論

本日の内容

• 1-1. この講義について
• 1-2. 計算可能性理論

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

1-1. この講義について

この講義では計算量理論の中でも特に reducibility (還元可能性)について議論します。

還元可能性はふたつの問題の難しさを比較する手法です。 例えば、問題 A と B が両方とも解き方が分かっていないときに、このふたつ の難しさを比較できるでしょうか？ これらの比較を行うのに、還元可能性を使います。または、一般には「帰着」 という言葉も使われます。 ある問題A とある問題 B に対して、もし B を解くプログラムがあったと仮定 した時、 A をそのプログラムを用いて解くことができることを示せれば、「A は B に帰着できる」と言います。これは本当に B が解ける必要はありません。 例えば、A として「 x は偶数である」という問題を考え、B として「 x の最 下位の桁の数は偶数である」という問題だとします。 この時、 x の最下位の桁が偶数であれば、 x 自体も偶数ですので、 A は B に帰着できます。

この「A は B に帰着できる」という考え方は問題の難しさにどう影響するの でしょうか？ もし B が解ければ、 A が解けるということは、 A は B 程難しくない ことを意味します。 また、 A を解くことができないことが示せれば、 B も解くことができません。 この意味でも B は A 以上に難しいことがわかります。 一方、「A は B に帰着でき」て、さらに「B は C に帰着できる」場合、帰着 の条件にもよりますが、「A は C に帰着できる」ことが示せます。 これは帰着という考え方が推移律を持つことを意味します。 以上のことから、帰着というのは一般の比較と同じ性質を持ちます。 つまり、「A ≤ B」と書いてなんの違和感もないということです。

帰着自体は手法を延べるため、一般的にはアルゴリズムになります。 つまり、問題を比較する一手法に、帰着させるアルゴリズムを与えるという方 法があるということです。

講義は二つの部分に分かれます。 前半は計算量理論周辺と暗号理論を取り上げ、オーソドックスな還元可能性に ついての結果を紹介します。 一方、後半は坂本の結果である、分散アルゴリズムの初期条件に関する情報量 の還元可能性による評価を紹介します。

1-2. 計算可能性理論

ある関数が計算可能(recursive 帰納的)とは、その関 数を計算するプログラムが作れ、どんな入力に対しても必ず停止し、答えを出 すことを言います(全射)。

参考資料

Hartley Rogers, Jr. "Theory of Recursive Functions and Effective Computability" the MIT Press(1987).

準備

本章では自然数の集合(0を含む)のみを扱います。

recursive function(帰納的関数)

f(x), g(x) など英字の関数記号を使う

集合 A に対する特性関数(Characteristic function)

c_Aで表し、次が成り立つ

$x\in A⟹c_A\left(x\right)=1$
$x\notin A⟹c_A\left(x\right)=0$

A がrecursive set

c_A が recursive function

Pairing function

x と y のpairing functionを $⟨x,y⟩$ で表します。 この関数は非負整数の組をひとつの非負整数に写像します(cf. p.64)。 これを繰り返すと、複数の数列をひとつの数に変換することができます。 したがって、記号でかかれたコンピュータプログラム全体もひとつの数で表す こともできます。 このような記述に対応する数を Gödel 数と呼びます。

記号の定義

${\phi }_x\left(y\right)$

Gödel 数 x のプログラムに y を入力したときに計算される値。 プログラムが止まらないときは値は未定義(↑)となる。また、停止するこ とを ↓ で表す。

あるいは y をパラメータとして見たときはプログラム x が計算する半関数 (止まらないときは未定義)。

$W_x=\text{domain}{\phi }_x$

プログラム x に対してプログラムが停止する入力の集合

$\mathrm{r.e.}=\left\{W_x\right\}$

recursive enumerable(帰納的可算)のクラス。 これに属する集合を recursive enumerable set と呼ぶ。

$D_x$

x 番目の有限集合(x を二進数だと思い、 i 桁目が 1 だったら i を含むと定 義する)

$K=\left\{x❘{\phi }_x\left(x\right)\downarrow \right\}=\left\{x❘x\in W_x\right\}$

停止問題

チャーチの提唱

人間が計算可能であることと、プログラムが計算可能であることが等価で あると考えること。 これは単にプログラムの計算能力の研究意義だけを考えるのではない。 証明中で、人間が計算可能であると判断できる時、具体的に全てのプログラム を与えない証明も許すということである。 例えば、pairing function のプログラムは具体的には与えないが、今後は pairing function を計算可能であるとして議論する。

recusive set と recursive enumerable set

定理 II(p.58)

$A$ が recursive enumerable かつ $\bar{A}$ (A の補集合)も recursive enumerable なら A は recursive

(逆は自明)

証明

$A$ を計算するプログラムの Gödel 数 を p、 $\bar{A}$ を計算するプログラムの Gödel 数 を q とする。 この時、入力 y に対して、 p と q を解釈し、 ${\phi }_p\left(y\right)$ と ${\phi }_q\left(y\right)$ を1 ステップずつ交互に計算するプログラムを作ることができる。 このようなプログラムを実行すると、どちらか一方だけは確実に止まり、もう 一方は止まらない。 pの方が止まったら 1、 q の方が止まったら 0 を出力すると、 c_A(y) を計算したことになる。 さらに、どのような入力に対しても必ず停止するので、これは recursive。 よって、 A は recursive set。

定理 VI(p.62)

K は recursive enumerable であるが、 recursive ではない

証明

まず K が recursive enumerable であることを示す。 入力 x について、 ${\phi }_x\left(x\right)$ を計算する半関数を $\psi \left(x\right)$ とおくと、これはプログラミング可能なので、ある定まった y に対して、 ${\phi }_y\left(x\right)=\psi \left(x\right)$ となる y がみつかる。 この ${\phi }_y$ の domain は K と一致する。

次に K が recursive でないことを示す。 定理 II より、 $\bar{K}$ が recursive enumerable でないことを示せば良い。 背理法の仮定として、 $\bar{K}=W_z$ となる z が存在するとする。 すると、以下のことが成り立つ。

1. $z\in K⟺z\in W_z$ (定義)
2. しかし、$\bar{K}=W_z$ となるように z を選んだので、両方の集合に含まれるか含まれないかは同値。 つまり $z\in \bar{K}⟺z\in W_z$

これを同時に満たすことは矛盾になる（対角線論法）。

reducibility(7章 p.80)

1-1, many-one

1-1 reducibility (A が B に 1-1 reducible)

ある 1-1 recursive function f が存在して、 $x\in A⟺f\left(x\right)\in B$

many-one reducibility (A が B に main-one reducible)

ある recursive function f が存在して、 $x\in A⟺f\left(x\right)\in B$

つまり、「A に含まれるかどうか」が f により「B に含まれるかどうか」に 変換できることを示します。例えば、

A:

偶数の集合

B:

下一桁が 0,2,4,6,8 の数

と置くと かつ が成り立ちます。

Turing reducibility

B を解くサブルーチン（関数）があれば A を解くプログラムが作れる時、 (A が B に Turing reducible)と言います。

補題

1-1 recursive function は recursive function なので自明。

入力 x に対して、 f(x) を計算した後、 x∈B をサブルーチンに計算さ せ、結果を出力させれば良いことになります。

以上のことからこの三つの reducibility において、一番条件が厳しいのは 1-1 で、一番緩いのは Turing となります。

completeness (p. 82)

(1-complete) A が に対して、complete

A が recursive enumerable で、かつ全ての recursive enumerable な B に 対して、

これは recursive enumerable set の中で A が一番難しいことを示します。

定理III

K₀ は 1-complete。 但し、 K₀は次で与えられる。 $K_0=\left\{⟨x,y⟩❘{\phi }_x\left(y\right)\text{がある}z\text{step 以内で停止する}\right\}$

証明

B をある recursive enumerable set とする。すると $B=W_{y_0}$ となる y₀ が存在する。 ある x が B に属するか否かは、 ${\phi }_{y_0}\left(x\right)$ がある z step 以内で停止するかどうかを調べれば良い。 これは $⟨y_0,x⟩\in K_0$ を調べれば良い。 ここで、入力 x から $⟨y_0,x⟩$ を求めるのは recursive で 1-1 で計算できるので、 が成り立つ。(Q.E.D.)

定理 IV

K は 1-complete

証明

を示せば良い。 そのために、 1-1 で K₀の元を K の元に一対一で対応付ける recursive function を構成する。 証明は p.82 参照

定理II(b)

は upper semi lattice

lattice とはこの場合任意のふたつの元 a, b に対して以下のことが成り立つ ことである。

1. a≤c, b≤c なる最小の c が存在する
2. d≤a, d≤b なる最大の d が存在する

このうち、最初の性質のみ成り立つのが upper semi lattice である。