Stone: Section 3

From CSWiki

Contents 1 Notation for composition and recursion 2 Primitive Functions 3 Combination Functions 4 Theorems

Notation for composition and recursion

Q. The notation being introduced for recursion and composition seems a bit tedious. In a way, I like its exactness, but is it really useful? The less formal definitions do almost as good a job of convincing me that a function is primitive recursive as the notation, once I know that composition and recursion are primitive recursive. Will it eventually be useful to manipulate the notation introduced for primitive recursive functions, or is it just being used to prove rigorously that functions are primitive recursive?

A. Later on, we'll see some function definitions that are much longer than the ones in the early sections. If they were presented in the conventional mathematical notation, they would be so long and diffuse that it would be difficult to understand their overall structure. (We could build them up a little at a time, but the intermediate-sized functions are not very interesting or memorable.) The concision of our notation will then be an important advantage.

There will also be some benefits when we start encoding primitive recursive functions as natural numbers -- the encoding scheme will directly reflect the syntactic structure of our procedures.

Primitive Functions

These are the building blocks of larger, primitive-recursive functions. They are:

• zero() = 0
• successor(x) = x+1
• - Note that here n is the number of inputs given to pr (i.e. the valence) and m is the zero-based index of the input we wish to project

Combination Functions

These functions are used to combine primitive functions into larger constructions. They are:

• Composition
  • If h(x₀,...,x_{n − 1}) = f(g₀(x₀,...,x_{n − 1}),...,g_{m − 1}(x₀,...,x_{n − 1})), then h is the composition function.
  • Basically, we are taking the output of m functions (here g₀...g_{m − 1}) and using them as the input for a new function, h.
  • Note that n is the valence of each of the subfunctions, g
  • Syntax: [o ] : g are subfunctions (their input is the input given to the composition function, and their ouput will be used as input for f); f is a function that will be called using the output of the gs; m is the number of subfunctions, g, and serves as the valence of f; n is the valence of each g as well as for the whole composition function
  • Example: Let h = [o], then h(5) is false as . h(0) is false as . h(6) is true as .
• Recursion
  • Basically, we perform a function g (described below) on the given input until the recursion variable, t, equals zero, at which point, we perform the function, f.
  • Note that g has three input groups, t (the variable of recursion), h(x₀,...,x_{n − 1},t) (the value of the last step of recursion), and x₀x₁...x_{n − 1} (the input)
  • Syntax: [] : f is the base function (what to do when t hits zero); g is the function that will be recursed; n is the valence of f
  • Note that recusion has a valence of n+1, as we give it n inputs as well as an initial value for t

Theorems

Theorem 3.1: add(x,y) is primitive recursive

 Similar to +, but as we only use natural numbers, the outcome is always natural.
 add(x,y) = x + y
 add(3,7) = 3 + 7 = 10

Theorem 3.2: double(x) is primitive recursive

 double(x) = 2 * x
 double(7) = 2 * 7 = 14

Theorem 3.3: multiply(x,y) is primitive recursive

 Similar to *, but again, we only use natural numbers, so the outcome is always natural.
 multiply(x,y) = x * y
 multiply(4,8) = 4 * 8 = 32

Theorem 3.4: raise-to-power(x,y) is primitive recursive

 raise-to-power(x,y) = xy
 raise-to-power(2,3) = 23 = 8
 x is the base
 y is the exponent

Theorem 3.5: predecessor(x) is primitive recursive

 As we are only dealing with natural numbers, it is important to know that we are defining the predecessor of zero to be zero.
 predecessor(x) = 0 if x==0; x - 1 otherwise
 predecessor(0) = 0
 predecessor(8) = 8 - 1 = 7

Theorem 3.6: subtract(x,y) is primitive recursive

 We use predecessor to define subtract and so all negative answers are set to be zero.
 subtract(x,y) = 0 if yx; x - y otherwise
 subtract(6,12) = 0
 subtract(5,2) = 5 - 2 = 3
 x is the minuend
 y is the subtrahend

(also known as "monus", as it bottoms out at 0)

Theorem 3.7: disparity(x,y) is primitive recursive

 Finds the (positive) difference between two numbers
 disparity(x,y) = x - y if xy; y - x otherwise
 disparity(8,5) = 8 - 5 = 3
 disparity(5,8) = 8 - 5 = 3