2005/11/09 志村先生 前回の最後に言った事 原始機能的関数には、合成だけでは作れない原始機能的関数がある => このような関数をどうやって作るか ? 関数φ_n を次のように定める φ_0(x) = x + 1 φ_{m+1}(x) = φ_m(1) φ_{m+1}(n+1) = φ_m(φ_{m_1}(n)) # where φ_{m+1}(x)=φ_m^{x}(φ_m(1)) であることに注意 # 具体的に φ_m を調べてみる φ_1(n) φ_1(0) = φ_0(1) = 1 + 1 = 2 φ_1(n+1) = φ_0(φ_1(n)) = φ_1(n)+1 よって φ_1(x) = x + 2 φ_2(n) φ_2(0)=φ_1(1)=3 φ_2(n+1) = φ_1(φ_2(n)) = φ_2(n)+2 よって φ_2(x) = 2x + 3 φ_3(n) φ_3(0)=φ_2(1)=5 φ_3(n+1) = φ_2(φ_3(n)) = 2φ_2(n)+3 φ_3(n+1) + 3 = 2φ_2(n)+6 = 2(φ_2(n)+3) よって φ_2(x) = 2^{x+3} - 3 φ_4(n) φ_4(0)=φ_3(1)=13 φ_4(n+1) = φ_3(φ_4(n)) = 2^{φ_4(n)+3} - 3 よって φ_4(n+1) + 3 = 2^{φ_4(n)+3} つまり、 16 2 2 .. x 個数 2 φ_4(n)=2 - 3 φ_1(n)=φ_0(φ_0(n)) ここでは、合成しか使っていない φ_2(n) ここからは、本質的に機能的定義が使われている。 基本関数から合成だけで作られるどんな関数 f(x_1,..,x_n) に対して 「十分な大きな x 」に対して f(x,x,..,x) < 2x + 3 となる。 # 「十分な大きな x 」というのがポイント # 基本関数 x+1 を n 回数合成すると x + n ができる # 小さな x 関しては、 2x + 3 < x+n となる場合が在りうる proof) # 合成の回数を調べればよい # もっと強力な次の命題を示す f(x_1,..,x_n) を作るのに、関数の合成を k 回使ったとする すると、 f(x_1,..,x_n) < max{x_1,..,x_n} + 2^{k+1} # 後の式は、k に関する適当な関数を取れば Okey ことを、 k についての帰納法 基本関数について成立することは明らか 0 x + 1 は当然 プロジェクション は、max の方で押える 合成 ( 複雑なものでやってもしょうがないので簡単な者で例示 ) f(x_1,x_2) = g(h_1(x_1,x_2),h_2(x_1,x_2)) とする。 f が k 回合成しているのなら g, h は k - 1 回合成している 帰納法の仮定より g(y_1,y_2) < max{y_1,y_2} + 2^k h_1(x_1,x_2) < max{x_1,x_2} + 2^k h_2(x_1,x_2) < max{x_1,x_2} + 2^k なので、 f(x_1,x_2) = g(h_1(x_1,x_2),h_2(x_1,x_2)) より < max{h_1(x_1,x_2),h_2(x_1,x_2)} + 2^k < max{max{x_1,x_2}+2^k,max{x_1,x_2}+2^k}+2^k = max{x_1,x_2}+2^{k+1} 後は、 f(x,..,x) < x + 2^{k+1} < 2x+3 の後半を示せばよいが、これは、 x > 2^{k+1} 時、成立するので、Okey # これは、一番優しい例、これを一般化して次の命題を示す f(x_1,..,x_n) が原始帰納法を m 回施して得られる原始帰納的関数ならば、 十分に大きな x に対して f(x,x,..,x) < φ_{m+2}(x) # φ_{m+2}(x) は、m + 1 の原始帰納法を適用している が成立する # この結果は、次のようなことを意味する # 「帰納法を m+1 回使って作った関数の中には、 # 帰納法を m 回と合成を使っただけでは作れない関数がある」 # つまり、 # 「原始帰納法を使うことには本質的」 # である # これの証明は、各々の n に関して、上と同様な方法を取る ## 上の方法では、与えられた不等式を直接示すのではなく、より精密な不等式を示し、それから、証明している。 ## 精密化した時にどのような関数を考えれば良いかがポイント f(x_1,..,x_n) が原始帰納法を m 回施して得られる関数のとき 十分な大きさの x_1,..,x_n に対して f(x_1,..,x_n) < φ_{m+2}(max{x_1,,x_n}) を示す。 補助命題として f(x_1,..,x_n) に対して、定数 k があって f(x_1,..,x_n) < φ_{n+1}^k(max{x_1,..,x_n}) が成立する ことを示す。 # 再び、合成の例 f(x_1,x_2)=g(h_1(x_1,x_2),h_2(x_1,x_2)) とすると、帰納法の仮定より g(y_1,y_2) < φ_{m+1}^{k'}(max{y_1,y_2}) h_1(x_1,x_2) < φ_{m+1}^{k_1}(max{x_1,x_2}) h_2(x_1,x_2) < φ_{m+1}^{k_2}(max{x_1,x_2}) なので f(x_1,x_2) < φ_{m+1}^{k'}(max{h_1(x_1,x_2),h_2(x_1,x_2)}) < φ_{m+1}^{k'}(max{φ_{m+1}^{k_1}(max{x_1,x_2}),φ_{m+1}^{k_2}(max{x_1,x_2})} # φ_{m+1}は単調増加なので.. < φ_{m+1}^{k'}(φ_{m+1}^max{k_1,k_2}(max{x_1,x_2})) = φ_{m+1}^{k'+max{k_1,k_2}}(max{x_1,x_2})) なので k'+max{k_1,k_2} とすればよい # 帰納法の例 ( 一番、単純な場合だけを示す ) f(0)=a f(x+1)=g(f(x),x) # f は m + 1 回とすると、g は m 回以下の帰納法で作られている 帰納法の仮定より g(x,y) < φ_{m}^k'(max{x,y}) となる k' がある # [気持] f(x+1)=g(f(x),x) だが、後の x を無視すれば # f(x+1)=g(f(x))=g^k(a) # よって、 # f(x+1)=g^k(a) < φ_m^{k'x}(a) # となると考えてよい。 f'(x) だいたい、φ^{k'x}(x) と同程度 また、 φ_m^{k'x)(a) < φ_{m+1}(k'x+k'') であり、適当に大きな k を考えると φ_{m+1}(k'x+k'') < φ_{m+1}^k(x) なので、全体として、φ_{m+1}^k(x) で押えられる。 あとは、 φ_{m+1}^k(x) < φ_{m_2}(x) となる x と k の関係だが、 x > max{k, φ_{m+1}(1)} の時、成立。 # 結局.. φ_m(x) を作るには m - 1 回の原始帰納法が必ず必要 # ということが解った。これから、次のようなことが言える 定理 ( Ackermann ) 計算可能だが、原始帰納的でない関数が存在する。 # 注意「計算可能」をきちんと定義しなければならない 次のような関数 ( Ackermann 関数 ) を考える A(0,y)=y+1 A(x_1,y)=A(x,1) A(x_1,y_1)=A(x,A(x_1,y)) # 実は、A(x,y) = φ_x(y) になっている。 proof) もし、A(x,y) が原始帰納的であるとする すると、原始帰納法を m 回数適用しているはずである。 すると、上記の定理より、ある K が存在して x > K ならば A(x,x) < φ_{m_2}(x) となるはずである。 ところが A(x,y) = φ_x(y) なので、 φ_{m+2}(x) = A(m+2,x) そこで、 x > K, m+2 を取ると A(x,x) < A(m+2,x) < A(x,x) となり、矛盾 # 「計算可能」の説明 # A(x,y) = φ_x(y) # であり、φ_x(y) は、原始帰納的なので、計算可能 # 結果的に、A(x,y) も計算可能ということになる。 上記の結果から、「原始帰納法以外に新しい関数を作る原理」が必要 # 例えば、上記の A のように 2 重帰納法 ( 関数の作り方に関する帰納法 ) # を追加すれば、拡大できるが、実は、それだけでは不十分 # 実は、3 重帰納法で作った関数は押えられない # それならば、任意の n 重帰納法を全て許せばよさそうだが、そうなると、今度は、対角線論法等で、これらに入らない関数が作れる # => このアプローチでは対応できないことが解る # => 新しい手順が必要 追加する内容に関しては、次回