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)
“You may try but you can never imagine what it is to have a man’s form of genius in you, and to suffer the slavery of being a girl.”
—George Eliot [Mary Ann (or Marian)
“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)