primitive recursive function（英語表記）primitiverecursivefunction

世界大百科事典（旧版）内のprimitive recursive functionの言及

【帰納的関数】より

…1931年，K.ゲーデルが原始帰納的関数として初めて定式化し，これを用いて不完全性定理の証明を得た。自然数｛0,1,2，……｝の上で定義され，自然数を値とする関数f(x₁，……，x_n)が，　f(x)＝x＋1　　……(1)　　f(x₁，……，x_n)＝q　(qは定数)　　……(2)　　f(x₁，……，x_n)＝x_i　(1≦i≦n)　　……(3)　　f(x₁，……，x_n)＝g(h₁(x₁，……，x_n)，……，　　h_m(x₁，……，x_n))　　……(4)　　(ここで，gはm変数の関数で，g,h₁，……，　　h_mはすでに与えられた関数)　(ここで，g,hはすでに与えられた関数で，　　n＝1のときg(　)は定数を表すものとする)を有限回適用して定義されるとき，原始帰納的関数primitive recursive functionという。次に，μyR(＊，y)は，命題R(＊，y)が成り立つようなyが存在するときそのようなyの最小数を値とし，そうでないときは値が定まらないものと規約する。…

※「primitive recursive function」について言及している用語解説の一部を掲載しています。

出典｜株式会社平凡社「世界大百科事典（旧版）」