( recursive function theory, mathematical logic)
- Function
- The class of recursive functions is the same as the class of computable functions, but it is reached by a completely different route. To the allowed operations of the class of primitive recursive functions we add the following:
- (minimization:) If f(x_1,...,x_n,y) is a recursive function, then so is g(x_1,...,x_n) = min { k : f(x_1,...,x_n,k) = 0 }.
Note that it may happen that for some particular values of x_1,...,x_n, f(x_1,...,x_n,y) is non-zero for all y. In this case, the value of g(x_1,...,x_n) is said to be undefined. Colloquially, g(x_1,...,x_n) goes into an infinite loop (think of a computer program calculating f(x_1,...,x_n,k) for each k, until it finds a zero). In particular, g(x_1,...,x_n) is generally a partial function: it is only defined for some values of its arguments.
In fact, it happens that any recursive function can be written down using minimization at most once (the other primitive recursive operations are used numerous times); this follows from proving that Turing machines can compute any recursive function, and then seeing that when you simulate a Turing machine using recursive functions, computing the state of the machine and its tape at time T is primitive recursive; to simulate the machine until it halts, one needs only add one minimization.
The fact that the definitions of computable functions and recursive functions are so different, yet the resulting class of functions is the same, leads to the Church Turing thesis.
- Set
- A subset L of the nonnegative integers such that there exists a recursive function f for which f(n)=1 if n is in L, and f(n)=0 otherwise. Note that such a function f must be defined for all values of its argument n.
|