Theory Of Computation (2160704)

Primitive Recursion Operation

• Suppose n ≥ 0, and g and h are functions of n and n + 2 variables, respectively.
• The function obtained from g and h by the operation of primitive recursion is the function f : Nⁿ + 1 -> N
  defined by the formulas f(X,0) = g(X) f(X, k + 1) = h(X, k, f(x, k)) for every X ∈ Nⁿ and every k = 0

Primitive Recursive Function

• The set PR of primitive recursive functions is defined as follows.
  1. All initial functions are elements of PR.
  2. For any k ≥ 0 and m ≥ 0, if f : N^k -> N and g₁, g₂, … , g_n : N^m -> N are elements of PR, then the function f(g₁, g₂, … , g_k) obtained from f and g₁, g₂, … , g_k by composition is an element of PR.
  3. For any n ≥ 0, any function g : Nⁿ + 1 -> N in PR, and any function h : Nⁿ + 2 -> N in PR, the function f : Nⁿ + 1 -> N obtained from g and h by primitive recursion is in PR.
  4. No other functions are in the set PR.

Example : Show that the function f(x, y) = x + y is primitive recursive

• We start with primitive recursive derivation for Add.
• If Add is obtained from g and h by primitive recursion, g and h must be functions of one and three variable, respectively
• The equations are:
  Add(x,0)=g(x)
  Add(x,k+1)=h(x,k,Add(x,k))
  Add(x, 0) should be x, and thus we may take g to be the initial function p₁¹
• In order to get x+k+1 from the three quantities x, k, x+k, we can simply take the successor of x+k.
• In other words, h(x, k, Add(x, k)) should be s(Add(x, k)).
• These means that h(x1, x2, x3) should be s(x3) or s(p₃³(x1, x2, x3))
• Therefore, a derivation for Add can be obtained as follow:
• f0=p₁¹ (an initial function)
• f1=s (an initial function)
• f2=p₃³(an initial function)
• f3= s(p₃³) (obtained from f1 and f2 by composition)
• f4= Add (obtained from f0 and f3 by composition)
• This way of ordering the five functions is not the only correct one.
• Any ordering in which Add is last and s and both precede s(p₃³) would work well.