In Reference 7 we develop the recursive functions of a class of symbolic expressions in terms of the conditional expression and recursive function formalism.
As an example of the use of recursive function definitions, we
shall give recursive definitions of a number of functions over the
integers. We do this for three reasons: to help the reader familiarize
himself with recursive definition, to show how much simpler in
practice our methods of recursive definition are than either Turing
machines or Kleene's formalism, and to prove that any partial
recursive function (Kleene) on the non-negative integers is in tex2html_wrap_inline551
where tex2html_wrap_inline491 contains only the successor function and the predicate
equality.
Let I be the set of non-negative integers {0,1,2,...} and denote the successor of an integer n by n' and denote the equality of integers tex2html_wrap_inline859 and tex2html_wrap_inline861 by tex2html_wrap_inline863 . If we define functions succ and eq by
displaymath869
then we write tex2html_wrap_inline491 = tex2html_wrap_inline877 . We are interested in tex2html_wrap_inline551 . Clearly all functions in tex2html_wrap_inline551 will have either integers or truth values as values.
First we define the predecessor function pred(not defined for n = 0) by
displaymath887
displaymath889
We shall denote pred(n) by tex2html_wrap_inline893
Now we define the sum
displaymath895
the product
displaymath897
the difference
displaymath899
which is defined only for tex2html_wrap_inline901 The inequality predicate tex2html_wrap_inline903 is defined by
displaymath905
The strict inequality m < n is defined by
displaymath909
The integer valued quotient m/n is defined by
displaymath913
The remainder on dividing m by n is defined by
displaymath919
and the divisibility of a number n by a number m,
displaymath925
The primeness of a number is defined by
displaymath927
where
displaymath929
The Euclidean algorithm defines the greatest common divisor, and we write
displaymath931
and we can define Euler's tex2html_wrap_inline933 -function by
displaymath935
where
displaymath937
tex2html_wrap_inline939 is the number of numbers less than n and relatively prime to n.
The above shows that our form of recursion is a convenient way of
defining arithmetical functions. We shall see how some of the
properties of the arithmetical functions can conveniently be derived
in this formalism in a later section.
