Normal Form Theorem
The T predicate can be used to obtain Kleene's normal form theorem for computable functions (Soare 1987, p. 15). This states there exists a primitive recursive function U such that a function f of one integer argument is computable if and only if there is a number e such that for all n one has
- ,
where μ is the μ operator and holds if both sides are undefined or if both are defined and they are equal. Here U is a universal operation (it is independent of the computable function f) whose purpose is to extract, from the number x (encoding a complete computation history) returned by the operator μ, just the value f(n) that was found at the end of the computation.
Read more about this topic: Kleene's T Predicate
Famous quotes containing the words normal, form and/or theorem:
“Love brings to light the lofty and hidden characteristics of the lover—what is rare and exceptional in him: to that extent it can easily be deceptive with respect to what is normal in him.”
—Friedrich Nietzsche (1844–1900)
“Form and function are a unity, two sides of one coin. In order to enhance function, appropriate form must exist or be created.”
—Ida P. Rolf (1896–1979)
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)