a computable function is any function that is a member of the class of mu-recursive functions. generally, a computable function may be defined informally and is used to refer to functions that algorithms can compute. the mu-recursive class of functions is a formal model which represents the same class of (computable) functions that is built from first principles.
given the convention that FALSE=0 and TRUE=1, predicates are just total functions whose values are always either 0 or 1. hence predicates are just total functions whose values are always either 0 or 1. and therefore, it makes perfect sense to say that some given predicate is or is not computable by def-comp-func
a relation is recursive primitive if its characteristic predicate is computable.
the close relation between predicates and sets, lets us use the language of sets in talking about solvable and unsolvable problems. for example, the predicate is the characteristic function of the set . to say that a set , where , belongs to some class of functions means that the characteristic function of belongs to the class in question. thus, in particular, to say that the set is computable or recursive is just to say that is a computable function. likewise, is a primitive recursive set if is a primitive recursive predicate.
we may denote the collection of all decidable sets as .
a recursive language is a recursive set for which an alphabet is defined. more formally, a recursive language is a recursive subset of where is some alphabet.
we sometimes use to denote an arbitrary partial function (that isnt necessarily, or hasnt yet been proved to be computable).
we write to denote a function of variables computed by a program .
note that would be identified with a program , but for a numbered program we use , which may also be written to emphasize the number , see not-numed-comp-func.
a total function is computable iff it is a mu-recursive function that is total.
the close relation between predicates and sets, lets us use the language of sets in talking about solvable and unsolvable problems. for example, the predicate is the characteristic function of the set . to say that a set , where , belongs to some class of functions means that the characteristic function of belongs to the class in question. thus, in particular, to say that the set is computable or recursive is just to say that is a computable function. likewise, is a primitive recursive set if is a primitive recursive predicate.
we may denote the collection of all decidable sets as .