原始帰納
primitive recursion
関数の再帰的定義のこと
Haskellでのfib定義のような普通の再帰関数をn項に一般化したもの
以下の定義で$ g,hが計算可能であれば、$ fも計算可能 定義
任意の関数
$ g:\mathbb{N}^{n-1}\rightarrow\mathbb{N}
$ h:\mathbb{N}^{n+1}\rightarrow\mathbb{N}
から、次のようにして定義される関数$ f:\mathbb{N}^n\rightarrow\mathbb{N}を構成する操作を原始帰納という
$ f(0,\vec{y})=g(\vec{y})
$ f(x+1,\vec{y})=h(x,f(x,\vec{y}),\vec{y})
表記の意味に注意
個数を特定しない変数の並び
$ \vec{x}:=x_1,\cdots,x_k
補足
イメージとしては、Haskellなどで再帰関数を定義する際の
一つ目、境界を定義する方の右辺を$ gとし、
二つ目、再帰的に定義する方の右辺を$ hとしている感じ
code:hs
fact 0 = 1 -- f 0 = g
fact n = n * fact(n-1) -- f n = h
表記
このfのことを$ \mathcal{Pr}[g,h] と書く
「関数のクラス$ Eが原始帰納に関して閉じている」とは
$ \forall f,g\in E\Rightarrow\mathcal{Pr}[f,g]\in E
関連
参考