recursive function

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 $\text{[math]}$ is some fixed number and
$\text{[math]}$ where $\text{[math]}$ is some given broken link: blk:def-total-func of two variables. then $\text{[math]}$ is said to be obtained from $\text{[math]}$ by primitive recursion, or simply recursion.
the more general case of primitive recursion with multiple variables is shown in broken link: blk:blk-mu-recursive-func-schema-5.
[cite:;taken from @computability_davis_1994 chapter 3.2 recursion]

the definitions recursive_function.html and recursive_function.html are the same, just taken from 2 different books.

godel defined a collection of number-theoretic functions $\text{[math]}$ that, according to his intuition, represented all the computable functions. his definition was as follows:

successor. the function $\text{[math]}$ given by $\text{[math]}$ is computable.
zero. the function $\text{[math]}$ given by $\text{[math]}$ is computable.
<<>>projections. the functions $\text{[math]}$ given by $\text{[math]}$ , $\text{[math]}$ , are computable.
composition. if $\text{[math]}$ and $\text{[math]}$ are computable, then so is the function $\text{[math]}$ that on input $\text{[math]}$ gives $\text{[math]}$ 5. <<>>primitive recursion: if $\text{[math]}$ and $\text{[math]}$ are computable, $\text{[math]}$ , then so are the functions $\text{[math]}$ , defined by mutual induction as follows: $\text{[math]}$ where $\text{[math]}$ .
unbounded minimization. if $\text{[math]}$ is computable, then so is the function $\text{[math]}$ that on input $\text{[math]}$ gives the least $\text{[math]}$ such that $\text{[math]}$ is defined for all $\text{[math]}$ and $\text{[math]}$ if such a $\text{[math]}$ exists and is undefined otherwise. we denote this by $\text{[math]}$

the functions defined by 1 through 6 are called the $\text{[math]}$ -recursive functions. the functions defined by 1 through 5 only are called the primitive recursive functions.
[cite:;taken from @kozen_automata_1997 lecture 36; the $\text{[math]}$ -recursive functions]

the constant functions $\text{[math]}$ are primitive recursive: $\text{[math]}$ - addition is primitive recursive, since we can define $\text{[math]}$ - this is a bona fide definition by primitive recursion: in rule broken link: blk:blk-mu-recursive-func-schema-5, take $\text{[math]}$ , and $\text{[math]}$ . then $\text{[math]}$ - multiplication is primitive recursive, since $\text{[math]}$

note how we used the function $\text{[math]}$ defined previously. we are allowed to build up primitive recursive functions inductively in this way.

exponentiation is primitive recursive, since $\text{[math]}$ - the predecessor function $\text{[math]}$ is primitive recursive $\text{[math]}$ - proper subtraction: $\text{[math]}$ 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: $\text{[math]}$ - the relations $\text{[math]}$ , and $\text{[math]}$ , considered as (0,1)-valued functions, are all primitive recursive; for example, $\text{[math]}$ - functions can be defined by cases. for example, $\text{[math]}$ is primitive recursive: $\text{[math]}$ - inverses of certain functions can be defined. for example, $\text{[math]}$ is primitive recursive: $\text{[math]}$ , where $\text{[math]}$ and $\text{[math]}$ is from the previous example. the function $\text{[math]}$ just continues to add 1 to its first argument $\text{[math]}$ until the condition $\text{[math]}$ is satisfied. this must happen for some $\text{[math]}$ . inverses of other common functions, such as square root, can be defined similarly.

observe that all primitive recursive functions are total, whereas a $\text{[math]}$ -recursive function may not be. there exist total computable functions that are not primitive recursive; one example is Ackermann's function:
$\text{[math]}$ [cite:;taken from @kozen_automata_1997 example 36.1]

more primitive recursive functions include:

$\text{[math]}$
$\text{[math]}$
$\text{[math]}$
$\text{[math]}$

the term recursion refers to a function $\text{[math]}$ defined by induction. we first define $\text{[math]}$ and hen define $\text{[math]}$ in terms of previously defined functions using as inputs $\text{[math]}$ and $\text{[math]}$ . for example, the factorial function $\text{[math]}$ is defined by the recursion schemes
$\text{[math]}$ 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-Gödel general recursive function. in 1931 Gö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 (broken link: blk:def-primitive-recursive-schema-5) below, which yields an inductive definition of $\text{[math]}$ using the preceding value $\text{[math]}$ and previously defined functions $\text{[math]}$ and $\text{[math]}$ . [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 $\text{[math]}$ of functions closed under the following schemes (1)-(5).

the successor function $\text{[math]}$ is in $\text{[math]}$ .
the constant functions $\text{[math]}$ are in $\text{[math]}$ , $\text{[math]}$ .
the identity functions $\text{[math]}$ , $\text{[math]}$ , are in $\text{[math]}$ .
(composition) if $\text{[math]}$ , then $\text{[math]}$ is in $\text{[math]}$ , where $\text{[math]}$ are functions of $\text{[math]}$ variables, $\text{[math]}$ , and $\text{[math]}$ is a function of $\text{[math]}$ variables.
<<>>(primitive recursion) if $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ where $\text{[math]}$ where $\text{[math]}$ , the $\text{[math]}$ variables treated as parameters, assuming $\text{[math]}$ and $\text{[math]}$ are functions of $\text{[math]}$ and $\text{[math]}$ variables, respectively. and $\text{[math]}$ is a function of $\text{[math]}$ variables. (in case $\text{[math]}$ , a 0-ary function is a constant function which is in $\text{[math]}$ by scheme 2).

[cite:;taken from @computability_soare_2016 definition 17.2.1]

[kleene 1952] showed that all the usual functions on $\text{[math]}$ are primitive recursive, including $\text{[math]}$ and limited subtraction $\text{[math]}$ ,
$\text{[math]}$

the class $\text{[math]}$ of $\text{[math]}$ -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 $\text{[math]}$ is a partial function, and $\text{[math]}$ then $\text{[math]}$ is in $\text{[math]}$ . (here $\text{[math]}$ diverges if there is no such $\text{[math]}$ . hence, $\text{[math]}$ may be nontotal.)

[cite:;taken from @computability_soare_2016 definition 17.2.4]

[cite:;taken from @computability_soare_2016 chapter 17 history of computability]

the constant function $\text{[math]}$ for all $\text{[math]}$ is primitive recursive.

this may be true by definition when considering recursive_function.html, but not when considering the axioms of recursive_function.html.
$\text{[math]}$ 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:
$\text{[math]}$

if we write $\text{[math]}$ , we have the recursion equations
$\text{[math]}$ we can rewrite these equations as
$\text{[math]}$ where $\text{[math]}$ . the functions $\text{[math]}$ , and $\text{[math]}$ are primitive recursive functions; in fact they are initial functions. also, $\text{[math]}$ 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 $\text{[math]}$ is primitive recursive.
[cite:;taken from @computability_davis_1994 chapter 3.4 some primitive recursive functions]

the recursion equations for $\text{[math]}$ are
$\text{[math]}$ this can be rewritten
$\text{[math]}$ here, $\text{[math]}$ is the zero function.
$\text{[math]}$ $\text{[math]}$ is $\text{[math]}$ , and $\text{[math]}$ are projection functions. notice that the functions $\text{[math]}$ , and $\text{[math]}$ are all primitive recursive functions, since they are all initial functions. $\text{[math]}$ is also primitive recursive, so $\text{[math]}$ is a primitive recursive function since it is obtained from primitive recursive functions by composition. finally, we conclude that
$\text{[math]}$ is primitive recursive.
[cite:;taken from @computability_davis_1994 chapter 3.4 some primitive recursive functions]

for $\text{[math]}$ , the recursion operations are
$\text{[math]}$ more precisely, $\text{[math]}$ , where
$\text{[math]}$ and
$\text{[math]}$ finally, $\text{[math]}$ is primitive recursive because
$\text{[math]}$ and multiplication is already known to be primitive recursive.
[cite:;taken from @computability_davis_1994 chapter 3.4 some primitive recursive functions]

for $\text{[math]}$ , the recursion equations are
$\text{[math]}$ note that these equations assign the value 1 to the "indeterminate" $\text{[math]}$ .
[cite:;taken from @computability_davis_1994 chapter 3.4 some primitive recursive functions]

the predecessor function $\text{[math]}$ is defined as follows:
$\text{[math]}$ .
the recursion equations for $\text{[math]}$ are simply
$\text{[math]}$ hence, $\text{[math]}$ is primitive recursive.
[cite:;taken from @computability_davis_1994 chapter 3.4 some primitive recursive functions]

the function $\text{[math]}$ is defined as follows:
$\text{[math]}$ this function should not be confused with the function $\text{[math]}$ , which is undefined if $\text{[math]}$ . in particular, $\text{[math]}$ is total, while $\text{[math]}$ is not.
we show that $\text{[math]}$ is primitive recursive by displaying the recursion equations:
$\text{[math]}$ [cite:;taken from @computability_davis_1994 chapter 3.4 some primitive recursive functions]

the function $\text{[math]}$ is defined as the absolute value of the difference between $\text{[math]}$ and $\text{[math]}$ . it can be expressed simply as
$\text{[math]}$ and thus is primitive recursive.
[cite:;taken from @computability_davis_1994 chapter 3.4 some primitive recursive functions]

$\text{[math]}$ is the "integer part" of the quotient $\text{[math]}$ . for example, $\text{[math]}$ and $\text{[math]}$ . the equation
$\text{[math]}$ shows that $\text{[math]}$ is primitive recursive. note that according to this equation, we are taking $\text{[math]}$ .
[cite:;taken from @computability_davis_1994 chapter 3.7 minimalization]

if $\text{[math]}$ is a primitive recursive relation then $\text{[math]}$ , defined as
$\text{[math]}$ is a primitive recursive function.

the function $\text{[math]}$ is primitive recursive

consider the function
$\text{[math]}$ $\text{[math]}$ is primitive recursive by unbounded_search_operator.html and so $\text{[math]}$ is primitive recursive aswell. and by primitive_recursive_predicate.html the function desired can be defined as:
$\text{[math]}$ is primitive recursive too.

the function
$\text{[math]}$ is primitive recursive.

consider the function
$\text{[math]}$ $\text{[math]}$ is primitive recursive because the relation $\text{[math]}$ is.

the function $\text{[math]}$ that generalizes the example $\text{[math]}$ 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 $\text{[math]}$ denote the length of digits in the binary representation of $\text{[math]}$ . we have
$\text{[math]}$ we have $\text{[math]}$ is primitive recursive, and exponentiality is primitive recursive as well as addition and multiplication and so $\text{[math]}$ is primitive recursive by composition.

the function giving the fibonacci sequence, i.e. $\text{[math]}$ , is primitive recursive.

let $\text{[math]}$ , if we show that $\text{[math]}$ is primitive recursive then we can simply define $\text{[math]}$ .
$\text{[math]}$ because we were able to define $\text{[math]}$ in terms of $\text{[math]}$ and other p.r. functions we know $\text{[math]}$ is p.r.