primitive recursive function

...In 1931, K. Gödel first formulated it as a primitive recursive function and used it to prove the incompleteness theorem. A function f ( x1 , ..., _xn ) defined on the natural numbers { ₀ , 1, 2 , ...} and with values ​​of the natural numbers is called a _primitive recursive function when _it is defined by applying f(x) = x + 1 ... (1) f(x1, ..., xn ) ₌ q ( _q is a constant ) ... ₍ 2 ) f ( x1 , ..., xn ) = xi ( ₁ < = i < = _n ) ... _{(3) f(x1, ..., xn} ) ₌ g ( _h1 ( x1 , ..., xn ), _... , hm _{(x1 ,} ..., _xn ) ) ... (4) (here, g is a function of m variables, _and g , h1 , ..., hm are functions that have already been given) (here, g and h are functions that have already been given, and when n = 1, g () represents a constant). Next, μ yR (*, y ) is defined as the minimum number of y 's such that proposition R (*, y ) holds, and is otherwise undefined.

*Some of the terminology explanations that mention "primitive recursive function" are listed below.

Source | Heibonsha World Encyclopedia 2nd Edition | Information

…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」について言及している用語解説の一部を掲載しています。

出典｜株式会社平凡社世界大百科事典 第２版について | 情報