再帰的関数、μ再帰関数とも言う

全域帰納的関数、部分帰納的関数、原始帰納的関数の総称

初期関数という小さな関数から始め、合成、原始帰納、最小化などを組み合わせて、複雑な関数を形成する

計算の実行順序は関数合成によって決まる

ex. h\circ g\circ fなら、f,g,hの順で適用される

こういう感じ ref p.59

#WIP ちゃんとかく

原始帰納関数のクラスPR\subseteq全域帰納関数のクラスR\subset部分機能関数のクラスP

クラスR, P, PRはいずれも

合成、原始帰納、最小化について閉じている

クラスR, Pはいずれも

原始帰納関数について閉じている

ということは部分帰納関数==帰納的関数？

RとPRの間にいる関数の例

計算可能な真部分関数

executable'

comp'

赤線と「計算可能」が一致する

本特有の単語なしで書き直す

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とは

初期関数を含み

合成、原始帰納に関して閉じている

ような最小のクラスのこと

関数f\in\mathrm{PR}を原始帰納的関数という

(5)部分関数のクラスPとは

初期関数を含み

合成、原始帰納、最小化に関して閉じている

ような最小のクラスのこと

関数f\in\mathrm{P}を部分帰納的関数という

(6)全域帰納関数のクラスRとは

\{f|f\mathrm{は全域関数}, f\in P\}をいう

関数f\in Rを全域帰納関数という

順番が逆だが、「クラスPの内、全域関数なもの」なので、Pより狭い