1
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.
Let f : A B and g : B C
Composition of f and g can then be expressed as:
g f:AC
(g f)(x) = g(f(x))
h(x) = g(f(x))
NB: In
general composition is not commutative:
( g f )(x) ( f g )(x)
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
h( x1, ... , xn) = g( f1(x1 ,..., xn), , fk(x1 ,..., xn) )
Base step
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
(partially) computable. (Proof by construction)
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
(1)
f( x , 0 ) = x
f(x , y+1 ) = f( x , y ) + 1
(2)
Input: f ( 3, 2 ) => f ( 3 , 1 ) + 1 => ( f ( 3 , 0 ) + 1 ) + 1 => ( 3 + 1 ) + 1 =>
5
Primitive Recursively Closed (PRC) class of functions.
Initial functions:
s(x) = x + 1
n(x) = 0
ui (x1 , , xn) = xi
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.
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 computable.
We have already seen the addition function,
which can be rewritten in LRR as follows:
sum( x, succ(y) ) => succ( sum( x , y)) ;
sum( x , 0 ) => x ;
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
recursion.
8
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)))
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
Power function
x0 = 1
x y+1 = x y * x
Predecessor
function
p (0) = 0
p(t+1)=t
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) ;
In LRR the predecessor is as follows:
pred(1) => 0 ;
pred(succ(x)) => x ;
11
x0=x
x ( t + 1) = p( x t )
|xy|=(xy)+(yx)
(x) = 1 x
if
x0
1
( x)
0 otherwise
dotsub(x,x) => 0 ;
dotsub(x,succ(y)) => pred(dotsub(x,y)) ;
What would be the output?
dotsub(succ(succ(succ(0))),succ(0))
abs(x,y) => sum(dotsub(x,y),dotsub(y,x)) ;
(x) => dotsub(1,x) ;
Output for the following?
a(succ(succ(0)))
a(null(0))
12
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
xy
x0=x
x ( t + 1) = p( x t )
if x y then x y = x y; else x y = 0
|xy|
(x)
|xy|=(xy)+(yx)
(x) = 1 x
13
