Computability - Models of Computation: Exploring the Power of Computing - page 232

Then, h 1 ( x 1 , x 2 , x 3 )= x 3 + 1. Now define f add ( x , y ) using primitive recursion, as follows:

f add ( x ,0 )= U 1 ( x )
f add ( x , y + 1 )= h 1 ( x , y , f add ( x , y ))

The role of h is to carry the values of x and y from one recursive invocation to another. To
determine the value of f add ( x , y ) from this definition, if y = 0, f add ( x , y )= x .If y> 0,
f add ( x , y )= h 1 ( x , y 1 )) . This in turn causes other recursive invocations of

f add . The infix notation + is used for f add ;thatis, f add ( x , y )= x + y .
Because the primitive recursive functions are defined over the non-negative integers, the
subtraction function f sub ( x , y ) must return the value 0 if y is larger than x ,anoperation
called proper subtraction .(Itsinfixnotationis ·

− 1, f add ( x , y −

and we write f sub ( x , y )= x · y .) It is

defined as follows:

f sub ( x ,0 )= U 1 ( x )
f sub ( x , y + 1 )= U 3 ( x , y , P ( f sub ( x , y )))

The value of f sub ( x , y ) is x if y = 0 and is the predecessor of f sub ( x , y 1 ) otherwise.

The integer multiplication function , f mult , is defined in terms of the function h 2 :

−

3

→ :

h 2 ( x 1 , x 2 , x 3 )= f add ( U 1 ( x 1 , x 2 , x 3 ) , U 3 ( x 1 , x 2 , x 3 ))

Using primitive recursion, we have

f mult ( x ,0 )= Z ( x )
f mult ( x , y + 1 )= h 2 ( x , y , f mult ( x , y ))

The value of f mult ( x , y ) is zero if y = 0 and otherwise is the result of adding x to itself y
times. To see this, note that the value of h 2 is the sum of its first and third arguments, x and
f mult ( x , y ) . On each invocation of primitive recursion the value of y is decremented by 1
until the value 0 is reached. The definition of the division function is left as Problem 5.26 .
Define the function f sign : ￿ so that f sign ( 0 )= 0and f sign ( x + 1 )= 1. To

show that f sign is primitive recursive it suffices to invoke the projection operator formally. A
function with value 0 or 1 is called a predicate .

→

5.9.2 Partial Recursive Functions
The partial recursive functions are obtained by extending the primitive recursive functions to
include minimalization. Minimalization defines a function f : ￿ n → in terms of a

second function g : ￿ n + 1 → by letting f ( x ) be the smallest integer y ∈ such that

g ( x , y )= 0and g ( x , z ) is defined for all z ≤ y , z ∈ .Notethatif g ( x , z ) is not defined

for all z ≤ y ,then f ( x ) is not defined. Thus, minimalization can result in partial functions.

DEFINITION 5.9.2 The set of partial recursive functions is the smallest set of functions contain-
ing the base functions that is closed under composition, primitive recursion, and minimalization.

A partial recursive function that is defined for all points in its domain is called a recursive
function .