2005/12/21 志村先生 [前回] # 原始帰納的関数の coding を作った # 原始帰納的関数の coding を利用して compute を定義した # 実は、compute が原始帰納的関数でないことを示した 次のような性質を満すφ(x,y) がある 任意の原始帰納関数 f(x_1,..,x_n) に対して、 ある自然数 e が存在し、 φ(e,(x_1,..,x_n))=f(x_1,..,x_n) # e は、f の定義に対応して作られる自然数 ( 前回やった coding ) となる。 # このφは、実は、原始帰納的でないことを前回証明した。 [定理] φ(x,y) は原始帰納的でない proof) もし、φ(x,y)が原始帰納的ならば、次の様に定義された g g(x)=φ(x,(x))+1 も原始帰納的である。 g が原始帰納的なので、g(x) に対して、自然 e が存在し φ(e,(x))=g(x)=φ(x,(x))+1 である。 ところが、これは、任意の x に対して成立するので、x に e を代入すれば φ(e,(e))=g(e)=φ(e,(e))+1 これは矛盾 # これは対角線論法 φ 自身は、原始帰納的ではないが、φの作り方から言えば、これは「計算可能」である 即ち、φは、「原始帰納的でないが計算可能である」具体的な例 # この一般化、即ち「原始帰納的」を「計算可能」に置き換えたらどうなるか ? # これは、「そのような関数は、計算可能でない」という結論を導くことになる !! 次のような性質を満すφ(x,y) がある 任意の「計算可能な関数」 f(x_1,..,x_n) に対して、 ある自然数 e が存在し、 φ(e,(x_1,..,x_n))=f(x_1,..,x_n) となる。 すると、同様な議論によって、 φ(x,y) は計算可能でない ことになる。 ところが、実際には、 φ(e,(x_1,..,x_n))=f(x_1,..,x_n) の右辺は、「計算可能」なので、その左辺が「計算可能でない」というのは変 # では、どこに問題が .. ? ## 一つの解釈は、「仮定が成立しない」すなわち、「e が存在しない」という事だが、話は、それほど、簡単ではない.. \psi(x,y) を次の様に定義する φ(x,y) x がある計算可能な f(x_1,..,x_n) に対応する数の時 \psi (x,y) = { 0 そうでないとき この \psi は、φと同じ性質がある !! # つまり、問題は、 「自然数 n が f(x_1,..,x_n) に対応しているかどうか」という「判定をする事」にあることが解る。 ## 元々 ( 関数 f に対応する.. ) 自然数 e は、その関数の定義から定めていたので、「そのような e がない」というのは変 # 以上の事実から、次のような考察が得られる。 f(x_1,..,x_n) の定義を視ただけでは、f(x_1,..,x_n) が計算可能かどうかが解らない # 原始帰納的関数では、実は、「定義を視ただけで」、言い替えれば、「定義さえできれば」実は、「計算可能」なものだけを扱っていた。 !!! 以上の結論は、「e の作り方に寄らない」という点も確認しておきたいポイント !!! つまり、coding の方法に問題があるわけではない == [部分帰納的関数] 定義 (最小化作用素) A(x_1,..,x_n,y) が自然数 x_1,..,x_n,y についての命題だとする この時、 z z が A(x_1,..,x_n,y) を満す、最小の y の時 \mu y.A(x_1,..,x_n,y) = { undefined A(x_1,..,x_n,y) を満す y が存在しないとき # 以前、「限定最小化作用素」を学んだが、それは、「範囲付けされた最小化作用素」になっていた。 ## この二つの違いは、「y の侯補の探す範囲の有無」 ## 探す範囲が限定されていれば、「みつからない」と判断できる ## 探す範囲が限定されていないと、「みつからない」は「とまらない」ということになってしまう。 ### ここでは、undefined の代りに 0 とする流儀もあるが、ここでは、undefined にしているのは、「とまらない」という気分を表している \mu y.A(x_1,..,x_n,y) は、n 変数の部分関数になっている # 「部分関数」というのは、全ての引数の値に対して、どの場合も値が定まる ( トータル / 全域な ) わけではない ( 部分的に定義されている.. ) ということ 定義 (部分帰納的関数) 1. (基本関数) z(x), s(x), p^n_i(x_1,..,x_n) は部分帰納的関数 2. (合成) g_1(x_1,..,x_n),..,g_2(x_1,..,x_n),..,g_k(x_1,..,x_n), h(x_1,..,x_k) が部分帰納的関数ならば、 f(x_1,..,x_n) \~= h(g_1(x_1,..,x_n),..,g_k(x_1,..,x_n)) も、部分帰納関数。 # ここで、右辺は、部分帰納関数なので、値が定義されていないかもしれない。 ただし、\~= の意味は、「右辺が定義されている時には、その値、そうでないとき ( つまり、g が定義されていなかったり、あるいは、g が定義されていても、その値の時、 h が定義されていない場合 ) は、undefind にする」の意味。 3. (帰納法) f(0,x_1,..,x_n) \~= g(x_1,..,x_n) f(x',x_1,..,x_n) \~= h(x,f(x,x_1,..,x_n),x_1,..,x_n) も、部分帰納関数。 # もしかしたら、これは、次の 4. で実現できるかも .. ?? 4. (\mu) f(x_1,..,x_n) \~= \mu y.(g(x_1,..,x_n,y)=0) も、部分帰納関数。 [定義] (帰納的関数) 部分帰納的関数 f(x_1,..,x_n) が全域的関数の時 f を帰納的関数 と呼ぶ # 実は、この「帰納的関数」が、「計算可能な関数」の意味 !! ## 「全域的」という「強制」があると、「計算が可能」ということが導かれる ◯ 部分帰納的関数の code は、原始帰納的関数と同様に定めることができる # 帰納的関数の場合は、compute が作れたが、部分帰納的関数の場合は、 # 巧く行きそうもない ( そもそも、「部分的」なので、計算できない場合 ( 結果が、undefined の時 ) があるので.. ) 計算木 (computation tree) x_1, .. x_n に特別な値 ( i_1,..,i_k ) を入れた時の f の値が k となる証拠 # これは、関数の定義に照し合せれば、作ることができる 1. f が、初期関数の時は、f そのものをみれば、解る 2. f が合成関数の時は、 f(x_1,x_2) \~= h(g_1(x_1,x_2),g_2(x_1,x_2)) # 一般に n としても繁雑なだけなので、n=2 でやる の時は、 k=f(i_1,i_2) の証拠は、 j_1=g_1(x_1,x_2), j_2=g_2(x_1,x_2) の証拠と k=h(j_1,j_2) の証拠 の三つから導くことができる。 k=f(i_1,i_2) ／ ｜ ＼ j_1=g_1(x_1,x_2) j_2=g_2(x_1,x_2) k=h(j_1,j_2) 3. f が帰納的関数の時 f(0,x_1)\~=g(x_1) f(x'x_1)\~=h(x,f(x,x_1),x_1) f(3,i_1) ／ ＼ h(3,j_1,i_1)=k f(2,i_1)=j_1 ／ ＼ h(2,j_2,i_1)=j_1 f(1,i_1)=j_2 ／ ＼ h(1,j_3,i_1)=j_2 f(0,i_1)=j_3 | g(i_1)=j_3 4. f(x)\~= \mu y (g(x,y)=0) f(i)=k / | .. | \ g(i,0)=j_0\ne0 g(i,1)=j_1\ne0 .. g(i,k)=0 # 木が作れれば、(その特定な値において..) 計算できることと同じ ## 木は、定義と、「具体的な値」を見れば、「途中までは、常に作れる」が、木が作れなくなった時点で、「計算ができない」ことになる ### ここでは、f(i)=k である ( つまり、少くても x=i の時に f(x) は定義されていることが解っている ) 場合だけ、議論している。 ### つまり、既に、「(その点においては..)計算できている」という保証があるという、「前提」があるので、「木が作れる」ことが保証される。 #### 「関数 f が x = i で定義されている」ということが、「f(i)=k の計算木の存在保証」になっている。 以上により、計算木の作り方が定義される。 計算木は、自然数のラベルが張られた有限木 自然数で code 化できる 次は、原始帰納的 code(e) e が部分帰納的関数の code tree(t) t がある部分帰納的関数の計算木の code tree(t) の時、 t から t が計算している部分帰納的関数のコード f の値のコード をそれぞれを取り出す関数 # これは、「計算木があれば、計算できる」ということを意味する [定理] f(x_1,..,x_n) が全域的 <=> どんな i_1, .., i_n に対しても f(i_1,..,i_n) の計算木が存在する proof) 計算木の定義から明らか [定義] ( kleene の T 述語 ) T(e,x_1,..,x_n,y) 1. e は n 変数の部分帰納的関数 f(x_1,..,x_n) の code 2. y は f(x_1,..,x_n) の値の計算木の code # e, y は原始帰納的に記述可能 # の時に真となる述語だとすると とすると、T(e,x_1,..,x_n,y) は原始帰納的(述語) # 与えられた e, x_1,..,x_n から y を求めるのは大変だが、 # y が与えられて、それが、e, x_1, .., x_n の計算結果になっているかどうか ? を判定するのは簡単 ## 「結果を作る」のではなく、「結果かどうかを判定」している点が味噌 !!! 「NP と P の関係」と同じ f が全域的 <=> \forall x_1,..,x_n \exist y T(e,x_1,..,x_n,y) ここで、計算木から、値を取り出す原始帰納的関数を U とすれば、 f(x_1,..,x_n) \~= U(\mu y.T(e,x_1,..,x_n,y)) # Kleene の標準形 となる。 これより、次のような事がいえる # ここでは、変数の個数を 1 つとしているが、勿論 n でも okey 部分帰納関数φ(u,x) が存在し、次のを満す任意の一変数部分帰納的関数 f(x) に対して、自然数 e が存在し、 φ(e,x) \~= f(x) となる。 # これは、compute の部分帰納関数版になるのだが.. ## 残念ながら、対角線論法が成立しない ### 実際.. 関数 g(x) を g(x) \~= φ(x,x)+1 と定義すれば、これは、部分帰納的で、 φ(e,x) \~= g(x) \~= φ(x,x)+1 となり、ここで、x=e とすると、 φ(e,e) \~= φ(e,e)+1 となるが、 これは、「矛盾」ではない。 単に φ(e,e) が undefined である ことを示している だけ である。 !!! undefined ではなく 0 と定義していると、ここでは違う結果に.. この結果得られる事実は φ(x,x) が全域的でない という結論 # この事実から、色々な性質が導かれる。 [Col.] \forall x \exist y T(x,x,y) でない # \exist T(x,x,y) は原始帰納的でない [Col.] 部分帰納的関数の code e から e が code 化している 関数が全域かどうかを知ることはできない # 「計算可能」に関しては、これらの内容が「常識」になっている。