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
.