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:
“A few ideas seem to be agreed upon. Help none but those who help themselves. Educate only at schools which provide in some form for industrial education. These two points should be insisted upon. Let the normal instruction be that men must earn their own living, and that by the labor of their hands as far as may be. This is the gospel of salvation for the colored man. Let the labor not be servile, but in manly occupations like that of the carpenter, the farmer, and the blacksmith.”
—Rutherford Birchard Hayes (1822–1893)
“In the name of Hippocrates, doctors have invented the most exquisite form of torture ever known to man: survival.”
—Luis Buñuel (1900–1983)
“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)