next up previous
Next: Computable Functionals Up: Formalisms For Describing Computable Previous: Functions Computable in Terms

Recursive Functions of the Integers


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



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



We shall denote pred(n) by tex2html_wrap_inline893

Now we define the sum


the product


the difference


which is defined only for tex2html_wrap_inline901 The inequality predicate tex2html_wrap_inline903 is defined by


The strict inequality m < n is defined by


The integer valued quotient m/n is defined by


The remainder on dividing m by n is defined by


and the divisibility of a number n by a number m,


The primeness of a number is defined by




The Euclidean algorithm defines the greatest common divisor, and we write


and we can define Euler's tex2html_wrap_inline933 -function by




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.

next up previous
Next: Computable Functionals Up: Formalisms For Describing Computable Previous: Functions Computable in Terms

John McCarthy
Wed May 1 20:03:21 PDT 1996