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:
“Separation anxiety is normal part of development, but individual reactions are partly explained by experience, that is, by how frequently children have been left in the care of others.... A mother who is never apart from her young child may be saying to him or her subliminally: “You are only safe when I’m with you.””
—Cathy Rindner Tempelsman (20th century)
“Driving is a spectacular form of amnesia. Everything is to be discovered, everything to be obliterated.”
—Jean Baudrillard (b. 1929)
“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)