μ-recursive function
From Wikipedia, the free encyclopedia
|
Other equivalent classes of functions are the λ-recursive functions and the functions that can be computed by Markov algorithms. The set of all recursive functions is known as R in computational complexity theory.
DefinitionThe μ-recursive functions (or partial μ-recursive functions) are partial functions that take finite tuples of natural numbers and return a single natural number. They are the smallest class of partial functions that includes the initial functions and is closed under composition, primitive recursion, and the μ operator. The smallest class of functions including the initial functions and closed under composition and primitive recursion (i.e. defined by use of the first five functions) is the class of primitive recursive functions. All primitive recursive functions are total functions. The sixth or "μ operator" is required because not all total functions that can be calculated can be done so with only the five primitive recursive functions (e.g. the Ackermann function ). In these instances the μ operator terminates the calculation. It serves as an unbounded search operator, unbounded but yet (by definition of a total function) shown by some means (e.g. an induction proof) to eventually produce a number and terminate the calculation. However, if the unbounded μ operator itself is partial -- that is, some numbers exist for which it fails to return a number -- the function that makes use of it will also be a partial function -- undefined for some numbers. In these instances, because it is unbounded, the μ operator will search forever, never terminating the calculation by producing a number. (Some algorithms may employ a u-operator that can produce the symbols "u" indicating "undecided" and thereby terminate the calculation (cf Kleene (1952) pp. 328ff)). Said another way: A partial μ-recursive function which uses a partial μ operator may not be total. The set of total μ-recursive functions is the subset of partial μ-recursive functions which are total. The first three functions are called the "initial" or "basic" functions: (In the following the subscripting is per Kleene (1952) p. 219. For more about some of the various symbolisms found in the literature see Footnote|Symbolism):
.
=def Failed to parse (Missing texvc executable; please see math/README to configure.): f(x_1,\ldots,x_k) = x_i .
and functions Failed to parse (Missing texvc executable; please see math/README to configure.): g_i(x_1,\ldots,x_k) for each i with Failed to parse (Missing texvc executable; please see math/README to configure.): 1 \le i \leq m and returns the function which maps x1, ... xk to
.
and Failed to parse (Missing texvc executable; please see math/README to configure.): h(y,z,x_1,\ldots,x_k) and returns the unique function Failed to parse (Missing texvc executable; please see math/README to configure.): f such that
,
.
and returns the function Failed to parse (Missing texvc executable; please see math/README to configure.): \mu y f(y,x_1,\ldots,x_k)
whose arguments are x1 , . . ., xk . The function Failed to parse (Missing texvc executable; please see math/README to configure.): f
is either a number-theoretic function from natural numbers { 0, 1, ... n } to natural numbers { 0, 1, ... n } or a representing function that operates on a predicate (with output { t, f } ) to yield { 0, 1 }.
such that f(0,x1,x2,...,xk), f(1,x1,x2,...,xk), ..., f(y,x1,x2,...,xk) are all defined and f(y,x1,x2,...,xk) = 0, if such an y exists; if no such y exists, then μy f is not defined for the particular arguments x1,...,xk. The strong equality operator Failed to parse (Missing texvc executable; please see math/README to configure.): \simeq is used to compare partial μ-recursive functions. This is defined for all partial functions f and g so that
holds if and only if for any choice of arguments either both functions are defined and their values are equal or both functions are undefined. The problem of decidabilityThe question immediately arises: Suppose the algorithm we design to calculate our numbers is not terminating? Do we or do we not have a "calculable" function? How would we decide this? Kleene describes it this way: We start with the notion of an "effectively decidable predicate":
Kleene proposes that "we can search through the propositions R(x,0), R(x,1), R(x,2), ... in succession, looking for one that is true, as far as we please...
So how do we determine if our misbehaving algorithm is "decidable"? Can we submit it to a "termination-analysis" algorithm that will render "the decision" YES or NO? The proof why the answer is "undecidable" is complex because of all the definitions. The point of it is that Kleene can enumerate all the total recursive functions and show, by Cantor's diagonal method, that more functions exist than can be defined recursively. An adventureous reader may want to read Footnote|Theorem IV. (For more background see the discussion at primitive recursive functions.) Theorem IV -- The enumeration theorem: We can enumerate (assign a number to) all the (total) recursive functions: The following is a verbal account of Kleene's theorem. In the following we abbreviate the string of n parameters (number-variables) x1, . . . xn as x. A predicate function yields { true, false } rather than a number. The quantifier expressions are Kleene's 'intuitive symbolism' (cf p. 225):
We start with a total μ-recursive function R(x, y). The fact that R is total μ-recursive means it is defined by a "system" (a sequence) of primitive recursive operators D and a mu operator E. Kleene calls this "system" F. F is equipped with the variables x that take place of the numbers we will use as parameters. For this F, Kleene shows how we can calculate a number f, the Gödel number of the system of equations F with the variables x embedded in the number. Suppose we have some natural numbers that we want to plug into the various x of our recursive function R. As our function R is total recursive we should be able to plug ANY numbers into the various xi and have our function R(x, y) yield a single number y as output (by the definition of a total μ-recursive function). This y represents the "the deduction Y" from F, given the parameters x. Ditto for a new predicate Tn that Kleene defines in terms of (i) the Gödel number f of "system of equations" F, (ii) system F's parameters x, and (iii) a final number y that should pop out after we choose some natural numbers to plug into the x and apply function Tn to f, x, and y:
Kleene shows that, given an f and an instance of parameters x, the predicate Tn is true for at most one Gödel number y. In other words, we don't expect that if f as the legitimate Gödel number of a system of equations F, that an single instance of parameters Tn would yield two or three numbers e.g. y1, y2, y3, or a different number y than we would get from R. From these considerations he derives the following "enumeration theorem": "Theorem IV: For each n ≥ 0: Given any general recursive predicate R(x, y), numbers f and g exist such that:
where Tn(z, x, y) is the particular primitive recursive predicate defined above...." (p. 281) Kleene describes the theorem this way:
Theorem V: There are more number-theoretic predicates than recursive functions Kleene now reduces the problem from a sequence of variables x a single variable x that will accept any natural number. By use of Cantor's diagonal argument, Kleene's Theorem V shows that there is a problem that appears when we let x = Gödel number f in the first formula and x = Gödel number g in the second formula. In other words, for its "parameter" x, we plug in the "system" F's very own Gödel number f. There is nothing that says we cannot do this; if the function Y (repesented by Gödel number y) is a total recursive function derivable from F (represented by Gödel number f) we should be able to plug in ANY number into x and satisfy the equation, but we cannot:
Kleene explains the proof this way:
The consequences with respect to algorithms: These results lead to two theorems with respect to algorithms:
And these lead to the following conclusions if we accept Church's thesis:
Thus we are confronted with the problem of undecidability -- the halting problem. There is no testing-algorithm we can build that will tell us "YES" = 0 or "NO" = 1, for all algorithms starting with Gödel number 1, whether each algorithm will terminate or not. When the testing algorithm arrives at its own number, it will not terminate. Kleene's answer to Hilbert's 2nd Problem:
Equivalence with other models of computability
Kleene's proof of the equivalence of "computable functions by Turing machine" to "partial functions" that are arrived by "use of the primitive recursive operators and the u-operator" can be expressed in its final form as a Theorem:
To prove formal equivalence, Kleene is required to prove the two parts of this Theorem XXX. Theorem XXVIII (Kleene pp. 363 ff) proceeds by showing how to convert the five primitive-recursive operators and the μ-operator to their Turing equivalents so a Turing machine can emulate an algorithm using the recursion operators. Theorem XXIX (Kleene pp 373-376) proceeds by arithematizing the actions of a Turing machine and showing that this number can be arrived at by use of various primitive recursive functions and a u-operator at the end to terminate the calculation. Equivalence of various computational models (e.g. register machines) usually proceed with a demonstration that the machine is equivalent to a Turing machine (i.e. two proofs are required -- for all instances (i) the machine-in-question implies a Turing machine AND (ii) a Turing machine implies the machine-in-question. As noted above: In the equivalence of models of computability, a parallel is drawn between Turing machines which do not terminate for certain inputs and an undefined result for that input in the corresponding partial recursive function. The unbounded search operator is not definable by the rules of primitive recursion as those do not provide a mechanism for "infinite loops" (undefined values). Normal form theoremA normal form theorem due to Kleene says that there for each k there are primitive recursive functions Failed to parse (Missing texvc executable; please see math/README to configure.): U(y)\! and Failed to parse (Missing texvc executable; please see math/README to configure.): T(y,e,x_1,\ldots,x_k)\! such that for any μ-recursive function Failed to parse (Missing texvc executable; please see math/README to configure.): f(x_1,\ldots,x_k)\! with k free variables there is an e such that
. The number e is called an index or Gödel number for the function f. A consequence of this result is that any μ-recursive function can be defined using a single instance of the μ operator applied to a (total) primitive recursive function. Minsky (1967) observes (as does Boolos-Burgess-Jeffrey (2002) pp. 94-95) that the U defined above is in essence the μ-recursive equivalent of the universal Turing machine:
FootnotesFootnote|SymbolismA number of different symbolisms are used in the literature. An advantage to using the symbolism is a derivation of a function by "nesting" of the operators one inside the other is easier to write in a compact form. In the following we will abbreviate the string of parameters x1, . . ., xn as x:
Example: Kleene gives an example of how to perform the recursive derivation of f(b, a) = b + a (notice reversal of variables a and b). He starting with 3 initial functions
He arrives at:
Footnote|Kleene Theorem IVTheorem IV: We can enumerate all the (total) recursive functions: In theorem IV (p. 281) he proves that, given a recursive function R(x, y) -- where x is our abbreviation for a string of n parameters (number-variables) x1, . . . xn, -- there exists a Gödel number f that can satisfy a special predicate T (i.e. T is a function yielding { true, false } ). By use of this predicate he can "enumerate" (assign a number to) all the recursive functions R(x, y) in the following manner: The definitions begin with this:
D is the system of equations that recursively define the representing function ψ of R. The (slightly expanded) system of equations F is defined as DE, where E represents the u-operator that terminates the calcuation.
f is the Gödel number of the system of equations F. y is the Gödel number of "an entity Y" deduced from F. A second equation is defined as follows:
Equating equations (2) and the one immediately above:
Kleene replaces Sn with a predicate Tn defined from it. The predicate means:
Thus we see that if y is a Gödel number of the deduction Y, then Tn is true for only this one y given Gödel number z. And Tn is primitive recursive, Sn is recursive. This allows Kleene to write:
Theorem IV: For each n ≥ 0: Given any general recursive predicate R(x, y), numbers f and g exist such that:
Kleene describes the theorem this way:
ExamplesSee alsoExternal linksReferences
cs:Částečně rekurzivní funkce de:Μ-Rekursion es:Función recursiva fr:Fonction récursive is:Endurkvæmt fall it:Funzione ricorsiva he:פונקציה רקורסיבית ja:μ再帰関数 pl:Funkcja rekurencyjna pt:Recursividade ru:Рекурсивная функция |
