January 14, 2010
Note regarding hand-in problem 1:
More on how to formally define a primitive recursive function
Formal Definitions of primitive recursive functions.
Note that in definitions of a function f by primitive recursion, the "h" function has one more argument than f, and the g function has one less argument. In a definition of a function f by composition from g and a set of h's the h functions will have as many arguments as f, and there will be as many h functions as the arity of g. See page 56 and 57.
Primitive recursive (p.r.) functions are recursively defined as being either base functions (nullary zero, unary successor or n-ary projection functions) , or defined from known p.r. functions by composition or recursion.
This means that in the definition of a (non-base) function f, either by composition or by primitive recursion, the functions that f is defined in terms of, must be already known to be primitive recursive. Cook's notes show how to do this in a top-down fashion, defining addition in terms of some functions that are then shown to be themselves a priori primitive recursive. Another way to do this is a bottom-up approach as follows:
- start a list of functions beginning with the zero, successor and projection functions (don't have to write these down)
- add any required intermediate functions to the list, provided they can be defined in terms of p.r. functions already on the list.
- continue until you can define the required function f either by composition or primitive recursion, again in terms of functions already on the list.
Make sure you understand the requirements for definition by composition on page 57, ditto primitive recursion. The most important thing is that these functions are defined in terms of already known primitive recursive functions.
Here is an example formal definition of addition in this format, note that "// " means rest of line is a comment:
Define g(x) = I1,1(x) //actually doesn't need to be defined, it already is p.r. since I11 is a base function
define h(x,y,z) = S(I33(x,y,z)) //defn by composition, here m=1 in the defn of composition, both I33 and S are p.r. functions
define plus(x,y) by primitive recursion from (already known to be p.r.) functions g and h as follows:
plus(x,o) = g(x) // = I11(x) = x
plus(x,y+1) = h( x,y,plus(x,y)) // = S(I33(x.y.z) = z+1 = plus(x,y) +1
Informally, it is common to omit projections, definitions of constants, zero functions of multiple arguments, etc. but formally, these should be shown to be primitive recursive prior to use in a definition.
In your solutions, you can include any function already shown to be primitive recursive in your list (such as plus) without bothering to show the existing p.r. functions that it is defined from. So in a definition of "mult" you can assume "plus" is already on your list, but you should make sure the other functions that mult is defined from (specifically the g and h) are already on the list before defining mult.
Hope this helps - PD