Primitive Recursive Functions
1
Preliminaries: partial and total functions
● The domain of a partial function on set A contains the subset of A.
● The domain of a total function on set A contains the entire set A.
● A partial function f is called partially computable if there is
some program that computes it. Another term for such
functions partial recursive.
● Similarly, a function f is called computable if it is both total
and partially computable. Another term for such function is
recursive.
2
Composition
●Let f : A → B and g : B → C
● Composition of f and g can then be expressed as:
g ͦ f:A→C
(g ͦ f)(x) = g(f(x))
h(x) = g(f(x))
●NB: In general composition is not commutative:
( g ͦ f )(x) ≠ ( f ͦ g )(x) 3
Composition
●Definition: Let g be a function containing k
variables and f1 ... fk be functions of n variables, so
the composition of g and f is defined as:
h(0) = k
Base step
h( x1, ... , xn) = g( f1(x1 ,..., xn), … , fk(x1 ,..., xn) )
Inductive step
Example: h(x , y) = g( f1(x , y), f2(x , y), f3(x , y) )
● h is obtained from g and f1... fk by composition.
● If g and f1...fk are (partially) computable, then h is 4
(partially) computable. (Proof by construction)
Recursion
● From programming experience we know that recursion refers
to a function calling upon itself within its own definition.
● Definition: Let g be a function containing k variables then
h is obtained through recursion as follows:
h(x1 , … , xn) = g( … , h(x1 , … , xn) )
Example: x + y
f( x , 0 ) = x
(1)
f(x , y+1 ) = f( x , y ) + 1 (2)
5
Input: f ( 3, 2 ) => f ( 3 , 1 ) + 1 => ( f ( 3 , 0 ) + 1 ) + 1 => ( 3 + 1 ) + 1 => 5
PRC: Initial functions
● Primitive Recursively Closed (PRC) class of functions.
● Initial functions: s(x) = x + 1 succ
n(x) = 0 zero
ui (x1 , … , xn) = xi projn
● Example of a projection function: u2 ( x1 , x2 , x3 , x4 , x5 ) = x2
● Definition: A class of total functions C is called PRC² class if:
● The initial functions belong to C.
● Function obtained from functions belonging to C by
either composition or recursion belongs to C. 6
PRC: primitive recursive functions
● There exists a class of computable functions that is a
PRC class.
● Definition: Function is considered primitive
recursive if it can be obtained from initial
functions and through finite number of
composition and recursion steps.
● Theorem: A function is primitive recursive iff it
belongs to the PRC class. (see proof in chapter 3)
● Corollary: Every primitive recursive function is 7
computable.
Primitive recursive functions: sum
● We have already seen the addition function, which can
be rewritten in LRR as follows:
f( x , 0 ) = x
sum( x, succ(y) ) => succ( sum( x , y)) ;
sum( x , 0 ) => x ; f(x , y+1 ) = f( x , y ) + 1
Example: sum(succ(0),succ(succ(succ(0)))) => succ(sum(succ(0),succ(succ(0)))) =>
succ(succ(sum(succ(0),succ(0)))) => succ(succ(succ(sum(succ(0),0) =>
succ(succ(succ(succ(0))) => succ(succ(succ(1))) => succ(succ(2)) => succ(3) => 4
NB: To prove that a function is primitive recursive you need show that it
can be obtained from the initial functions using only concatenation and 8
recursion.
Primitive recursive functions: multiplication
h( x , 0 ) = 0
h( x , y + 1) = h( x , y ) + x
● In LRR this can be written as:
mult(x,0) => 0 ;
mult(x,succ(y)) => sum(mult(x,y),x) ;
● What would happen on the following input?
mult(succ(succ(0)),succ(succ(0)))
9
Primitive recursive functions: factorial
0! = 1
( x + 1 ) ! = x ! * s( x )
●LRR implementation would be as follows:
fact(0) => succ(null(0)) ;
fact(succ(x)) => mult(fact(x),succ(x)) ;
Output for the following? fact(succ(succ(null(0))))
10
Primitive recursive functions:
power and predecessor
Power function In LRR the power function can
be expressed as follows:
pow(x,0) => succ(null(0)) ;
pow(x,succ(y)) => mult(pow(x,y),x) ;
Predecessor
In LRR the predecessor is as follows:
function
pred(1) => 0 ;
p (0) = 0
p(t+1)=t pred(succ(x)) => x ;
11
Primitive recursive functions:
∸, | x – y | and α
dotsub(x,x) => 0 ;
x∸0=x dotsub(x,succ(y)) => pred(dotsub(x,y)) ;
x ∸ ( t + 1) = p( x ∸ t ) What would be the output?
● dotsub(succ(succ(succ(0))),succ(0))
|x–y|=(x∸y)+(y∸x) abs(x,y) => or(dotsub(x,y),dotsub(y,x)) ;
α(x) = 1 ∸ x α(x) => dotsub(1,x) ;
Output for the following?
● a(succ(succ(0)))
12
● a(null(0))
Primitive recursive functions
x+y f( x , 0 ) = x
f( x , y + 1 ) = f( x , y ) + 1
x*y h( x , 0 ) = 0
h( x , y + 1 ) = h( x , y ) + x
x! 0! = 1
( x + 1 )! = x! * s(x)
x^y x^0 = 1
x^( y + 1 ) = x^y * x
p(x) p( 0 ) = 0
p( x + 1 ) = x
x∸y x∸0=x
if x ≥ y then x ∸ y = x – y; else x ∸ y = 0 x ∸ ( t + 1) = p( x ∸ t )
|x–y| |x–y|=(x∸y)+(y∸x)
α(x) α(x) = 1 ∸ x 13
