lpetrich
Contributor
A primitive recursive function is one with a limited set of control-flow statements: if-then-else and looping with the maximum number of times to loop known before starting the loop.
Most familiar algorithms can be expressed as PRF's.
A PRF has the nice property that its runtime is guaranteed to be bounded.
A general recursive one relaxes the constraint on number of times to loop. It can be arbitrarily large, and its maximum need not be known before entering the loop.
General recursive functions are equivalent to Turing machines, and in turn, to the lambda calculus: doing everything with functions.
I will illustrate some operations in the lambda calculus, but using "normal" function notation
Boolean operations:
true(x,y) = x
false(x,y) = y
ifelse(x,a,b) = x(a,b)
and(x,y) = x(y,x)
or(x,y) = x(x,y)
not(x,a,b) = x(b,a)
not(true,a,b) = true(b,a) = b = false(a,b)
For numbers, one uses Peano's axioms, getting the nonnegative integers as 0 with an arbitrary number of successors of it.
num(0,f,x) = x
num(1,f,x) = f(x)
num(2,f,x) = f(f(x))
num(3,f,x) = f(f(f(x)))
...
successor(n,f,x) = f(n(f,x))
Arithmetic:
plus(m,n,f,x) = m(f,n(f,x))
times(m,n,f,x) = m(n(f,arg),x)
One can express recursion with something called the Y combinator.
Most familiar algorithms can be expressed as PRF's.
A PRF has the nice property that its runtime is guaranteed to be bounded.
A general recursive one relaxes the constraint on number of times to loop. It can be arbitrarily large, and its maximum need not be known before entering the loop.
General recursive functions are equivalent to Turing machines, and in turn, to the lambda calculus: doing everything with functions.
I will illustrate some operations in the lambda calculus, but using "normal" function notation
Boolean operations:
true(x,y) = x
false(x,y) = y
ifelse(x,a,b) = x(a,b)
and(x,y) = x(y,x)
or(x,y) = x(x,y)
not(x,a,b) = x(b,a)
not(true,a,b) = true(b,a) = b = false(a,b)
For numbers, one uses Peano's axioms, getting the nonnegative integers as 0 with an arbitrary number of successors of it.
num(0,f,x) = x
num(1,f,x) = f(x)
num(2,f,x) = f(f(x))
num(3,f,x) = f(f(f(x)))
...
successor(n,f,x) = f(n(f,x))
Arithmetic:
plus(m,n,f,x) = m(f,n(f,x))
times(m,n,f,x) = m(n(f,arg),x)
One can express recursion with something called the Y combinator.