Primitive recursive function

In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose all loops are 'for' loops (that is, a upper bound of the number of iterations of every loop can be determined before entering the loop). Primitive recursive functions form a strict subset of those general recursive functions that are also total functions. In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose all loops are 'for' loops (that is, a upper bound of the number of iterations of every loop can be determined before entering the loop). Primitive recursive functions form a strict subset of those general recursive functions that are also total functions. The importance of primitive recursive functions lies on the fact that most computable functions that are studied in number theory (and more generally in mathematics) are primitive recursive. For example, addition and division, the factorial and exponential function, and the function which returns the nth prime are all primitive recursive. In fact, for showing that a computable function is primitive recursive, it suffices to show that its computational complexity is upper bounded by a primitive recursive function of the input size. It follows that it is difficult to devise a computable function that is not primitive recursive, although some are known (see the section on Limitations below). The set of primitive recursive functions is known as PR in computational complexity theory. The primitive recursive functions are among the number-theoretic functions, which are functions from the natural numbers (nonnegative integers) {0, 1, 2, ...} to the natural numbers. These functions take n arguments for some natural number n and are called n-ary. The basic primitive recursive functions are given by these axioms: More complex primitive recursive functions can be obtained by applying the operations given by these axioms: Example. We take f(x) as the S(x) defined above. This f is a 1-ary primitive recursive function. And so is g(x) = S(x). So h(x) defined as f(g(x)) = S(S(x)) is a primitive recursive 1-ary function too. Informally speaking, h(x) is the function that turns x into x+2. Example. Suppose f(x) = P11(x) = x and g(x,y,z)= S(P23(x,y,z)) = S(y). Then h(0,x) = x and h(S(y),x) = g(y,h(y,x),x) = S(h(y,x)). Now h(0,1) = 1, h(1,1) = S(h(0,1)) = 2, h(2,1) = S(h(1,1)) = 3. This h is a 2-ary primitive recursive function. We can call it 'addition'. Interpretation. The function h acts as a For loop from 0 up to the value of its first argument. The rest of the arguments for h, denoted here with xi’s (i = 1, ..., k), are a set of initial conditions for the For loop which may be used by it during calculations but which are immutable by it. The functions f and g on the right side of the equations which define h represent the body of the loop, which performs calculations. Function f is only used once to perform initial calculations. Calculations for subsequent steps of the loop are performed by g. The first parameter of g is fed the “current” value of the For loop’s index. The second parameter of g is fed the result of the For loop’s previous calculations, from previous steps. The rest of the parameters for g are those immutable initial conditions for the For loop mentioned earlier. They may be used by g to perform calculations but they will not themselves be altered by g.