Characteristic Function in Recursion Theory, Gödel's and Kleene's representing Function
Kurt Gödel described the representing function in his 1934 paper "On Undecidable Propositions of Formal Mathematical Systems". (The paper appears on pp. 41-74 in Martin Davis ed. The Undecidable):
- "There shall correspond to each class or relation R a representing function φ(x1, . . ., xn) = 0 if R(x1, . . ., xn) and φ(x1, . . ., xn)=1 if ~R(x1, . . ., xn)." (p. 42; the "~" indicates logical inversion i.e. "NOT")
Stephen Kleene (1952) (p. 227) offers up the same definition in the context of the primitive recursive functions as a function φ of a predicate P, takes on values 0 if the predicate is true and 1 if the predicate is false.
For example, because the product of characteristic functions φ1*φ2* . . . *φn = 0 whenever any one of the functions equals 0, it plays the role of logical OR: IF φ1=0 OR φ2=0 OR . . . OR φn=0 THEN their product is 0. What appears to the modern reader as the representing function's logical-inversion, i.e. the representing function is 0 when the function R is "true" or satisfied", plays a useful role in Kleene's definition of the logical functions OR, AND, and IMPLY (p. 228), the bounded- (p. 228) and unbounded- (p. 279ff) mu operators (Kleene (1952)) and the CASE function (p. 229).
Read more about this topic: Indicator Function
Famous quotes containing the word function:
“Uses are always much broader than functions, and usually far less contentious. The word function carries overtones of purpose and propriety, of concern with why something was developed rather than with how it has actually been found useful. The function of automobiles is to transport people and objects, but they are used for a variety of other purposes—as homes, offices, bedrooms, henhouses, jetties, breakwaters, even offensive weapons.”
—Frank Smith (b. 1928)