再帰的関数
Definition
初期関数に対して以下を行って作られる関数は再帰関数という．
合成
最小化とは次のことを指す
$ \psi: \N^{k+1} \mapsto \Nのとき，
$ \varphi: \N^k \mapsto \Nとし，
全ての$ z<yで$ \psi(\vec{x},z) \neq 0で$ \psi(\vec{x},z)=0な$ yが存在する時，$ \varphi(\vec{x}) = y
存在しない時，未定義すなわち$ \varphi(\vec{x}) = \botとする．
すなわち$ \psi(\vec{x},y)=0となるような最小の値$ yが存在するならそれを$ \varphi(\vec{x})の値とし，存在しないなら$ \varphi(\vec{x}) = \botとする．
このプロセスを，$ \varphi(\vec{x}) = \mu y.\lbrack \psi(\vec{x},y)=0 \rbrackと書く．
$ \varphiを，$ \psiから定まる最小化という．
注意
$ A \sube \N^nに対して関数$ \chi_A(\vec{x}):\N^n \mapsto \{0,1\}を，
$ \vec{x} \in Aなら$ \chi_A(\vec{x}) = 0
$ \vec{x} \notin Aなら$ \chi_A(\vec{x}) = 1
$ A \sube \N^nに対して，$ Aの特性関数$ \chi_Aが再帰的なら，$ Aは再帰的集合あるいは計算可能であるという． $ A = \{ \vec{x} \in \N^n : \varphi(\vec{x}) = 0\}な再帰的関数$ \varphi:\N^n\mapsto\{0,1\}が存在するとき，$ Aは再帰的可算集合という． 参考文献