the term "recursive function" in computability seems to be used loosely and defined differently by different books, but the general consensus seems to be that mu-recursive functions (in reference to kleene's mu-operator), aliased partial recursive functions are defined as the complete class of recursive functions which is proved to represent the class of algorithmically computable functions (functions that can be computed by a machine) and the primitive recursive functions are a subset of that class restricted to total functions. the term recursive function usually seems to refer to the more general class of computable functions (the former).
suppose
is some fixed number and
where
is some given def-total-func of two variables. then
is said to be obtained from
by primitive recursion, or simply recursion.
the more general case of primitive recursion with multiple variables is shown in blk-mu-recursive-func-schema-5.
the definitions def-mu-recursive-functions and def-mu-recursive-functions-2 are the same, just taken from 2 different books.
godel defined a collection of number-theoretic functions
that, according to his intuition, represented all the computable functions. his definition was as follows:
- successor. the function
given by
is computable.
- zero. the function
given by
is computable.
- blk-mu-recursive-func-schema-3/projections/. the functions
given by
,
, are computable.
- composition. if
and
are computable, then so is the function
that on input
gives
blk-mu-recursive-func-schema-5/primitive recursion/: if and are computable, , then so are the functions , defined by mutual induction as follows:
where .
- unbounded minimization. if
is computable, then so is the function
that on input
gives the least
such that
is defined for all
and
if such a
exists and is undefined otherwise. we denote this by
the functions defined by 1 through 6 are called the
-recursive functions. the functions defined by 1 through 5 only are called the primitive recursive functions.
- the constant functions
are primitive recursive:
addition is primitive recursive, since we can define
this is a bona fide definition by primitive recursion: in rule blk-mu-recursive-func-schema-5, take , and . then
multiplication is primitive recursive, since
note how we used the function
defined previously. we are allowed to build up primitive recursive functions inductively in this way.
exponentiation is primitive recursive, since
the predecessor function
is primitive recursive
- proper subtraction:
is primitive recursive, and can be defined from predecessor in exactly the same way that addition is defined from successor. the sign function is primitive recursive:
the relations , and , considered as (0,1)-valued functions, are all primitive recursive; for example,
- functions can be defined by cases. for example,
is primitive recursive:
inverses of certain functions can be defined. for example, is primitive recursive: , where
and is from the previous example. the function just continues to add 1 to its first argument until the condition is satisfied. this must happen for some . inverses of other common functions, such as square root, can be defined similarly.
observe that all primitive recursive functions are total, whereas a
-recursive function may not be. there exist total computable functions that are not primitive recursive; one example is Ackermann's function:
more primitive recursive functions include:
the term recursion refers to a function
defined by induction. we first define
and hen define
in terms of previously defined functions using as inputs
and
. for example, the factorial function
is defined by the recursion schemes
where we assume that multiplication has been previously defined.
up until the early 1930s, the term "recursive function" meant what we now call a primitive recursive function to distinguish it from the Herbrand-Gödel general recursive function. in 1931 Gödel used primitive recursive functions in the proof of his famous incompleteness theorem and called them simply by the German term "rekursiv." the main property of recursion is the primitive recursion scheme (V) below, which yields an inductive definition of
using the preceding value
and previously defined functions
and
. [Kleene 1952] put the primitive recursive functions in the following succinct form which has become standard.
the class of primitive recursive functions is he least class
of functions closed under the following schemes (1)-(5).
- the successor function
is in
.
- the constant functions
are in
,
.
- the identity functions
,
, are in
.
- (composition) if
, then
is in , where are functions of variables, , and is a function of variables. def-primitive-recursive-schema-5(primitive recursion) if and , then where
where , the variables treated as parameters, assuming and are functions of and variables, respectively. and is a function of variables. (in case , a 0-ary function is a constant function which is in by scheme 2).
[kleene 1952] showed that all the usual functions on
are primitive recursive, including
and limited subtraction
,
the class
of
-recursive (partial) functions is the least class obtained by closing under schemes (1)-(5) for the primitive recursive functions and the following scheme (6).
- (unbounded search) if
is a partial function, and
then is in . (here diverges if there is no such . hence, may be nontotal.)
(taken from robert i. soare, 2016 chapter 17 history of computability)
the constant function
for all
is primitive recursive.
this may be true by definition when considering def-primitive-recursive, but not when considering the axioms of def-mu-recursive-functions.
we can gain intuition by looking at it in the form of a matrix of functions, in which all items in the same column are equal and each column corresponds to the successor of the value corresponding to the column on its left:
if we write
, we have the recursion equations
we can rewrite these equations as
where
. the functions
, and
are primitive recursive functions; in fact they are initial functions. also,
is a primitive recursive function, since it is obtained by composition of primitive recursive functions. thus, the preceding is a valid application of the operation of recursion to primitive recursive functions. hence
is primitive recursive.
the recursion equations for
are
this can be rewritten
here,
is the zero function.
is
, and
are projection functions. notice that the functions
, and
are all primitive recursive functions, since they are all initial functions.
is also primitive recursive, so
is a primitive recursive function since it is obtained from primitive recursive functions by composition. finally, we conclude that
is primitive recursive.
for
, the recursion operations are
more precisely,
, where
and
finally,
is primitive recursive because
and multiplication is already known to be primitive recursive.
for
, the recursion equations are
note that these equations assign the value 1 to the "indeterminate"
.
the predecessor function
is defined as follows:
.
the recursion equations for
are simply
hence,
is primitive recursive.
the function
is defined as follows:
this function should not be confused with the function
, which is undefined if
. in particular,
is total, while
is not.
we show that
is primitive recursive by displaying the recursion equations:
the function
is defined as the absolute value of the difference between
and
. it can be expressed simply as
and thus is primitive recursive.
is the "integer part" of the quotient
. for example,
and
. the equation
shows that
is primitive recursive. note that according to this equation, we are taking
.
if
is a primitive recursive relation then
, defined as
is a primitive recursive function.
the function
is primitive recursive
consider the function
is primitive recursive by the-bounded-min and so
is primitive recursive aswell. and by def-prim-recurs-def-by-cases the function desired can be defined as:
is primitive recursive too.
the function
is primitive recursive.
consider the function
is primitive recursive because the relation
is.
the function
that generalizes the example
because 3 is 11 in binary form, and 100 is 4 in binary, which gives 11100 in binary which is the binary representation of the decimal 28.
let
denote the length of digits in the binary representation of
. we have
we have
is primitive recursive, and exponentiality is primitive recursive as well as addition and multiplication and so
is primitive recursive by composition.
the function giving the fibonacci sequence, i.e.
, is primitive recursive.
let
, if we show that
is primitive recursive then we can simply define
.
because we were able to define
in terms of
and other p.r. functions we know
is p.r.