Topic 5: Part-recursive functions
Recursive functions - historically the first formalization of the concept of algorithm. In the theory of recursive functions adopted a constructive approach, whose main feature is that the set of objects that are studied, based on a finite number of elementary objects with simple operations, effective feasibility are fairly obvious. Operations on functions called operators.
The function f(x1, x2, … , xn) is called partially numerical n-seater function if its domain of definition and the region is a subset of its values Nn . If the domain of the function = Nn , then the function f is everywhere defined. Calculated called numerical function f(x1, x2, … , xn) , whose value can be calculated by some algorithm based on the known values of the argument. Simplest is called such everywhere defined functions including:
O (x) = 0 (zero function), S (x) = x +1 (the continuity of the function)
Inm (x1, x2, … , xn) = xm , where m = 1, 2, ... , n
(projection function, selective function or feature selection).
Operator superposition Snm called substitution function in m variables f(x1, x2, … , xm) m functions f1(x1, x2, … , xn), ... , fm(x1, x2, … , xn) n the same variables. It sets a new function n variables.
They say that the operator of primitive recursion Rn defines the (n +1)-triple function f(x1, x2, … , xn, y) through n-seater function j(x1, x2, … , xn) and (n +2) - double function w(x1, x2, … , xn, y, z) so (according to primitive recursion): f(x1, x2, … , xn, 0) = j(x1, x2, … , xn);
f(x1, x2, … , xn, y+1) = w(x1, x2, … , xn, y, f(x1, x2, … , xn, y)).
Then say: f(x1, x2, … , xn, y) = Rn (j, w).
The function is called primitive recursive if it can be formed from the elementary functions using a finite number of applications of superposition operators and primitive recursion.
Consider the calculated n-bed partially numerical function f(x1, x2, … , xn) . Record a certain value x1, x2, … , xn-1 of its first (n-1) arguments and consider the equation f(x1, x2, … , xn-1, y) = xn . Than solve consistently value f(x1, x2, … , xn-1, y) for y = 0, 1, 2, .... Least a, for which f(x1, x2, … , xn-1, а) = xn, denoted as follows:
qy (f(x1, x2, … , xn-1, а) = xn).
The obtained expression defines a partial function variables x1, x2, … , xn, which determines the operator to minimize (q-operator). Often the operator to minimize consider uncertain. The function f(x1, x2, … , xn) is called partial-recursive if it can be formed from the elementary functions using a finite number of applications of operators of superposition, primitive recursion and minimization. Everywhere defined partially recursive function call general recursive.
You can easily install all recursivetion primitive logic functions: on the functional completeness of this set of functions and that the superposition of a primitive recursive operator.
Consider the set A, which is a subset of N. Characteristic function of set A are called cA function cA (x), which equals 1 if x is A and 0 otherwise. The set A is called primitive recursive if its characteristic function - primitive recursive.
Part-characteristic function cЧА set A called function cЧА (x), which equals 1 if x is A and is undefined otherwise. The set A is called partial-recursive if its characteristic function partially - partially-recursive. Obviously, the characteristic and partially characteristic functions coincide only for the set of natural numbers N. One can prove that every primitive recursive set is partially recursive.
Theorem:
Let f (x) - primitive-recursive function, and A - some primitive recursive set. Then the partial function defined by the scheme: fx(x) = f (x), if x is A and is uncertain if x Is not is partially recursive.
Theorem allows the construction of numerous examples of partially-recursive functions. General notion of partial-recursive functions - one of the main concepts of the theory of algorithms. On the one hand, each part of the standard set-recursive function is calculated for a specific procedure that meets the intuitive idea of the algorithm, on the other - that would still not built precisely defined classes of algorithms, always find out that the number of features that are calculated by the algorithms these classes were partially recursive. So common is this a scientific hypothesis (Church thesis): Class algorithmically calculated partial numerical functions coincides with the class of all partially recursive functions.
In the formulation of this thesis is an intuitive notion obchyslyuvanosti because it can neither prove nor disprove in general-mathematical sense. It is a fact which testifies in favor of long mathematical practice.
Theorem:
The system of functions {O (x), S (x)} is a relatively complete system of operations of superposition, primitive recursion and minimization of the set of algorithmically calculated partial numerical functions.
Partial recursivetion - a clarification of the notion of the function is performed. This concept can prove or refute resolution ofing.
