 This section presents definitions of the major classes of recursively defined functions studied in computability theory. Of these the primitive recursive functions \(\mathbf{PR}\) and the partial recursive functions \(\mathbf{PartREC}\) are the most fundamental. The former are based on a formalization of the process of recursion described in the introduction to this entry and include virtually all number theoretic functions studied in ordinary mathematics. The partial recursive functions are formed by closing the primitive recursive functions under the operation of unbounded minimization—i.e., that of searching for the smallest witness to a decidable predicate.  The class of  recursive functions  \(\mathbf{REC}\)—i.e., the partial recursive functions which are defined on all inputs—has traditionally been taken to correspond via Church’s Thesis  (Section 1.6) to those which can be effectively computed by an algorithm. 