帰納的関数
recursive function
計算の実行順序は関数合成によって決まる
ex. $ h\circ g\circ fなら、$ f,g,hの順で適用される
こういう感じ ref 『(理論)12 計算モデルの基礎理論』.icon p.59
https://gyazo.com/2c4d457967076b3ada6d4c9059d6d794
原始帰納関数のクラスPR$ \subseteq全域帰納関数のクラスR$ \subset部分機能関数のクラスP
クラスR, P, PRはいずれも
合成、原始帰納、最小化について閉じている
クラスR, Pはいずれも
原始帰納関数について閉じている
ということは部分帰納関数==帰納的関数？
RとPRの間にいる関数の例
executable'
comp'
赤線と「計算可能」が一致する
https://gyazo.com/961c3393473750efd2946a894774c582
本特有の単語なしで書き直すmrsekut.icon
$ Eは数値関数のクラス
(1)以下を満たすとき「$ Eは合成について閉じている」という $ \forall f,g_1,\cdots,g_n\in E\Rightarrow \lambda \vec{x}.f(g_1(\vec{x})),\cdots,g_n(\vec{x}))\in E
(2)以下を満たすとき「$ Eは原始帰納に関して閉じている」という $ \forall f,g\in E\Rightarrow\mathcal{Pr}[f,g]\in E
(3)以下を満たすとき「$ Eは最小化に関して閉じている」という $ \forall \lambda y\vec{x}.g(y,\vec{x})\in E\Rightarrow \lambda\vec{x}.\mu y[g(y,\vec{x})]\in E
(4)原始帰納関数のクラスPRとは
初期関数を含み
合成、原始帰納に関して閉じている
ような最小のクラスのこと
(5)部分関数のクラスPとは
初期関数を含み
合成、原始帰納、最小化に関して閉じている
ような最小のクラスのこと
(6)全域帰納関数のクラスRとは
$ \{f|f\mathrm{は全域関数}, f\in P\}をいう
順番が逆だが、「クラスPの内、全域関数なもの」なので、Pより狭い