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:
“You know that fiction, prose rather, is possibly the roughest trade of all in writing. You do not have the reference, the old important reference. You have the sheet of blank paper, the pencil, and the obligation to invent truer than things can be true. You have to take what is not palpable and make it completely palpable and also have it seem normal and so that it can become a part of experience of the person who reads it.”
—Ernest Hemingway (1899–1961)
“This conflict between the powers of love and chastity ... it ended apparently in the triumph of chastity. Love was suppressed, held in darkness and chains, by fear, conventionality, aversion, or a tremulous yearning to be pure.... But this triumph of chastity was only an apparent, a pyrrhic victory. It would break through the ban of chastity, it would emerge—if in a form so altered as to be unrecognizable.”
—Thomas Mann (1875–1955)
“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)