スマートフォン用の表示で見る

帰納的関数

サイエンス

帰納的関数

きのうてきかんすう

自然数から自然数への関数で、具体的に値を計算するアルゴリズムが存在するもの。

λ記法?を使って書くと、

  1. 初期関数
  2. 関数の合成
  3. 原始帰納法
  4. 最小化
    • g:n+1変数関数とする。
    • f=¥lambda x_1,...,x_n¥[¥min ¥{y ¥in N|g(x_1,...,x_n,y)=0¥}¥]
    • m=¥min ¥{y ¥in N|g(x_1,¥ldots,x_n,y)=0¥} が存在し、尚且つ任意の y¥leq m に対して g(x_1,¥ldots,x_n,y)¥downarrow のとき、そのときに限り f(x_1,¥ldots,x_n)¥downarrow
    • によって定義される関数fを、gから最小化により定義されたといい、¥mu y.g(x_1,¥ldots,x_n,y) と書く。

1,2,3,4を適用して作られた関数帰納的関数といい、その中で4の適用が無かったものを原始帰納的関数と呼ぶ。

帰納的関数であれば、whileのみを使ったプログラムで計算が可能である。また、原始帰納的関数であれば、loop(for)のみを使ったプログラムで計算が可能である。

全域帰納的だが原始帰納的でない関数としてアッカーマン関数が例としてしばしば挙げられる。

なお条件3を除いた最小化は一般に帰納的ではない。1-変数帰納的関数 f(x) を考える。ここで次のような関数を考えよう:g(N,x)=¥begin{cases} &1& &¥text{if $x¥lt N$}& ¥¥ &f(x)-f(x)& &¥text{if $x=N$}& ¥¥ &0& &¥text{otherwise}& ¥end{cases} これは帰納的関数である。条件3を除いた最小化 ¥mu x.g(N,x)帰納的関数だと仮定しよう。もし ¥mu x.g(N,x)¥neq N ならばそのときに限り f(N)¥uparrow であるから、これは``停止問題の補問題の半決定手続きが存在する"ことを意味する。停止問題は半決定可能であったから、したがって停止問題は決定可能となるが、これは停止問題の決定不可能性と矛盾する。したがって条件3を除いた最小化 ¥mu x.g(N,x)帰納的関数ではない。条件3が上の証明を破綻させることを確認しておこう。もし条件3に従えば、f(N)¥uparrow ならば ¥mu x.g(N,x)¥uparrow であるからそもそも ¥mu x.g(N,x)¥neq N が停止せず、したがって停止問題の補問題も半決定できない。

具体例

足し算

¥rm{add} = ¥lambda x y ¥[x+y¥]

  • ¥rm{add}(x,0) = U_{1}^{1} (x)
  • ¥rm{add}(x,y+1) = S(U_{3}^{3})(x,y,¥rm{add}(x,y))

掛け算

¥rm{mult} = ¥lambda xy¥[x ¥cdot y¥]

  • ¥rm{mult}(x,0) = Z(x)
  • ¥rm{mult}(x,y+1) = ¥rm{add}(U_{3}^{3},U_{1}^{3})(x,y,¥rm{mult}(x,y))

*リスト:リスト::数学関連