Recursiveness
Recursiveness
The notion of definition by recursion, and in particular of definition by primitive recursion, is explained in the article recursion, definition by. An n-adic function f (from non-negative integers to non-negative integers) is said to be defined by composition in terms of the m-adic function g and the n-adic functions h1, h2, . . . , hm by the equation
f(x1, x2, . . . , xn) = g(h1((x1, x2, . . . , xn),
h2(x1, x2, . . . , xn) = hm (x1, x2, . . . , xn)).
(The case is not excluded that m = 1, or n = 1, or both.)
A function from non-negative integers to non-negative integers is said to be primitive recursive if it can be obtained by a succession of definitions by primitive recursion and composition frorn the following list of initial functionsthe successor function S, the function C such that C(x) = 0 for every non-negative integer x, and the functions Uin (i = n, n = 1, 2, 3, . . . ) such that Uin(x1, x2, . . . , xn) = xi. Each successive definition by primitive recursion or composition may employ not only the initial functions but also any of the functions which were introduced by previous definitions.
More general notions of recursiveness result from admitting in addition to primitive recursion, also more general kinds of definition by recursion, including those in which several functions are introduced simultaneously by a single set of recursion equations. The most general such notion is that of general recursiveness — see the first paper of Kleene cited below. Notions of recursiveness may also be introduced for a function whose range consists of only a portion of the non-negative integers (in the case of a monadic function) or of only a portion of the ordered sets of n non-negative integers (in the case of an n-adic function) — see the second paper of Kleene cited.
Concerning the relationship between general recursiveness and the notion of effectiveness, see the article logistic system. — A.C.
R. Peter, a series of papers (in German) (in the Mathematische Annale, vol. 110 (1934), pp. 612-632; vol. 111 (1935), pp. 42-60; vol. 113 (1936), pp. 489-527. S. C. Kleene, General recursive functions of natural numbers, Mathematische Annalen, vol. 112 (1936), pp. 727- 742. S. C. Kleene, On notation for ordinal numbers, The Journal of Symbolic Logic, vol. 3 (1938), pp. 150-155.