CIS705a Assignment 3B

Question 3. Many simple operations on numbers are simple recursive; here's one:

def isEven(n): if n == 0 : true
               else : not(isEven(n - 1))

The general format of a simple-recursive function is this:

f(0) = j,  where  j  is some number
f(i + 1) = g(f(i)),  where  g is a (closed, nonrecursive or simple-recursive)
                     function that maps a number to a number.

An easy math induction proof shows, for any n >= 0, that f(n) = g(g(...g(j)...)), where g is repeated n times. For this reason, loops of the form, for N times do C, are simple-recursive functions.

We show that isEven is simple recursive by writing it in the equational format like this:

isEven(0) = true
isEven(n+1) = not(isEven(n))

We can encode simple-recursive functions in lambda-notation. Define [isEven] as a lambda-expression using the standard codings of [true], [false], [eq0], and [not]. Then, use it to compute ([isEven] [3]).

Question 4. There is a larger, more computationally powerful class of functions called the primitive-recursive functions..

Let X be a tuple of m parameter names, e.g., (x1,x2,..,xm). An m+1-argument primitive-recursive ("p.r.") function has this format:

It is a constant function, e.g., f(X) = k; or a projection function, e.g., f(X) = X[i], for 0<i≤n
It is the composition of already-defined p.r. functions, e.g., f(X) = h(g1(X),...gn(X)), for m-ary p.r. functions gi and n-ary p.r. function h.

It is defined with this schema: f(X, 0) = h(X), where h is an n-argument p.r. function f(X, n+1) = g(X, n, f(X, n)), where g is an n+2-argument p.r. function

Here is an example, the unary summation function on nonnegative ints: def sumTo(n) : if n == 0 : 0 else : n + sumTo(n-1)
and here is its presentation that shows it is primitive recursive in one argument: sumTo(0) = 0 sumTo(i + 1) = ADD1(i, sumTo(i)), where ADD1(a,b) = (a + 1) + b , which is a p.r. function in two arguments: it is built by composition using + which is also a p.r. function in two arguments. (Technically speaking, a and b are "projection functions" and 1 is a "constant function")

All the fundamental operations of arithmetic (+, -, >, ==, ...) are primitive recursive. (This is all of Peano arithmetic.) A primitive recursive function is guaranteed to terminate when called.

With math induction, we can prove, for all n >= 0, that a p.r. function of one argument computes to

f(n) = g(n-1, g(n-2, ... g(0, h(0))...))

where there are n uses of g. We can also prove that f(n) computes exactly the same answer as this while-loop: count = 0 ans = h(0) while count != n do: ans = g(count, ans); count = count + 1 print ans

There is a pattern for formatting a primitive-recursive function of one argument into a lambda-expression, by using pairs. Recall that

[pair] == lam e1. lam e2. lam b. b e1 e2

[fst] == lam p. p [true]

[snd] == lam p. p [false]

We see that [fst]([pair] E1 E2) => E1 [snd]([pair] E1 E2) => E2
We will use [pair] to model a two-variable storage vector, ([pair] count ans), and use it to build the above while-loop!

Here is how we code the pattern for f above:

lam n. [snd] (n  F ([pair] [0] [j]))
                  where  F is coded   lam p. ([pair] ([succ]([fst] p)) (G p))
                  and  G  is the coding of function  g

([pair] [0] [j]) is the starting value of the storage vector; F is the coding of the loop body, and n is the control of the number of loop iterations.

Here is the complete translation of sumTo into the lambda-calculus:

[sumTo] ==
lam n.  [snd] (n  (lam p. [pair] ([succ]([fst] p)) ([ADD1] p)) ([pair][0][0]) )

        where  [ADD1] == lam q. ([succ]([fst] q)) [succ] ([snd] q)

It is not so easy to see, but ([ADD1] ([pair] [i] [j])) => [i+1+j]
Try a few examples and confirm this.

Compute ([sumTo] [3]).

Question 5. Many functions are not primitive recursive (e.g., Fibonacci's and Ackermans's functions, as well as any function that is partially terminating). The general form of while-loop falls in this group. With simple- and primitive-recursive functions, one knows exactly how many times the computation will repeat/unfold when it starts. This is not true with the general-recursive functions. A function is general recursive if it can be written with equations and recursions of any combination.

Here is a famous example of a general-recursive function that is not primitive recursive --- Ackermann's function, which takes two arguments to compute its answer:

ack 0 n = n+1
ack (m+1) 0 = ack m 1
ack (m+1) (n+1) = ack m (ack (m+1) n)

It is more common to code the equations like this: def ack(m,n): """both m and n range over the nonnegative ints""" if m == 0: return n+1 elif n == 0: return ack(m-1, 1) else: return ack(m-1, ack(m, n-1))
It is possible to prove that this function always terminates, even though it cannot be formatted as primitive recursive.

A simple and famous example is Collatz's function, whose input is a positive int:

collatz(1) = 1
collatz(2 * i) =  collatz(i),   where int i > 0
collatz((2*i) + 1) = collatz((6 * i) + 4),  where  int i > 0

This can be coded as a loop! read(x) assert x > 0 while x > 1 : if x % 2 == 0 : x = x / 2 else : x = 3 * x + 1 print(x)
Collatz claimed, for every positive int, n, that collatz(n) == 1. But he and no one since has been able to prove this. It is a frustrating open problem in computing.

Examples like ack collatz, and while-loops are coded in lambda-calculus with the Y operator:

[Y] =  lam f. (lam z. f (z z))(lam z. f (z z))

The key property of Y is that Y F => (K K), where K = (lam z. F (z z)), and then K K => F(K K) =>* F(F(K K)) =>* F(F(F(K K))) =>* ..., etc. In this way, (Y F) "clones itself" and feeds itself to F. We use this behavior to model a general recursive function, which "clones itself" each time it restarts with a recursive call.

Code this function in lambda calculus, using Y:

haltEven(n) = if isEven(n) then 0
                           else haltEven(n+2)

(Note: use the coding of isEven from Question 3.) Use your definition of [haltEven] to reduce these expressions: ([haltEven] [0]) ([haltEven] [2]) ([haltEven] [1])