February 21, 2019
Theory of Computation Lecture 6: Primitive Recursive Functions I
1
Composition
Let uscombinecomputable functions in such a way that the output of one becomes an input to another.For example, we could combine the functions f and g to obtain a new function h:h(x) = f(g(x))Let us now take a more general view:Definition:Let f be a function of k variables and let g1, …, gkbe functions of n variables. Leth(x1, …, xn) = f(g1(x1, …, xn), …, gk(x1, …, xn)).Then h is said to be obtained from f and g1, …, gkbycomposition.
February 21, 2019
Theory of Computation Lecture 6: Primitive Recursive Functions I
2
Composition
Theorem 1.1:If h is obtained from the (partially) computable functions f, g1, …, gkby composition, then h is (partially) computable.Proof:The following program obviously computes h:Z1← g1(X1, …, Xn):Zk← gk(X1, …, Xn)Y ← f(Z1, …, Zk)If f, g1, …, gkare not only partially computable but are also total, then so is h. ■
February 21, 2019
Theory of Computation Lecture 6: Primitive Recursive Functions I
3
Composition
Example:We know that f(x1, x2) = x1+ x2is a computable function.We also know that g1(x) = x2and g2(x) = 3x are computable functions.According toTheorem 1.1, the following function h(x) must then also be computable:h(x) = f(g1(x), g2(x)) = f(x2, 3x) = x2+ 3x
February 21, 2019
Theory of Computation Lecture 6: Primitive Recursive Functions I
4
Recursion
Let k be some fixed number andh(0) = kh(t + 1) = g(t, h(t)) ,where g is some given total function of two variables.Then we say that h is obtained from g byprimitive recursion, or simplyrecursion.Theorem 2.1:Let h be obtained as shown above, and let g be computable. Then h is also computable.
February 21, 2019
Theory of Computation Lecture 6: Primitive Recursive Functions I
5
Recursion
Proof:Obviously, the function f(x) = k is computable.The program computing f(x) simply consists of k times the instruction Y ← Y+1.This gives us the macro Y ← k.Now we can write a program that computes h(x):Y ← k[A] IF X=0 GOTO EY ← g(Z, Y)Z ← Z+1X ← X-1GOTO A ■
February 21, 2019
Theory of Computation Lecture 6: Primitive Recursive Functions I
6
Recursion
Here is a similar, but more complicated type of recursion:h(x1, …, xn, 0) = f(x1, …, xn)h(x1, …, xn, t + 1) = g(t, h(x1, …, xn, t), x1, …, xn) .Here we say that that the function h of n + 1 variables is obtained byprimitive recursion(orrecursion) from the functions f (of n variables) and g (of n + 2 variables).Theorem 2.2:Let h be obtained from f and g as shown above, and let f and g be computable. Then h is also computable.
February 21, 2019
Theory of Computation Lecture 6: Primitive Recursive Functions I
7
Recursion
Proof:The following program computesh(x1, …, xn, xn+1):Y ← f(X1, …, Xn)[A] IF Xn+1=0 GOTO EY ← g(Z, Y, X1, …, Xn)Z ← Z+1Xn+1← Xn+1-1GOTO A ■
February 21, 2019
Theory of Computation Lecture 6: Primitive Recursive Functions I
8
PRC Classes
Now that we have learned aboutcompositionandrecursion, let us consider the functions that can be constructed with these operations.Let us define the followinginitial functions:s(x) = x + 1n(x) = 0uin(x1, …, xn) = xi, 1 ≤ i ≤ n.The functions uinare calledprojection functions.For example, u23(x1, x2, x3) = x2.
February 21, 2019
Theory of Computation Lecture 6: Primitive Recursive Functions I
9
PRC Classes
Definition:A class of total functionsCis called aPRC (primitive recursively closed) classifthe initial functions belong toC,a function obtained from functions belonging toCby either composition or recursion also belongstoC.Theorem 3.1:The class of computable functions is a PRC class.
February 21, 2019
Theory of Computation Lecture 6: Primitive Recursive Functions I
10
PRC Classes
Proof:We already know through Theorems 1.1, 2.1, and 2.2 that applying composition or recursion to computable functions results in further computable functions.Therefore, we only have to show that theinitial functionsare computable.Obviously, s(x) = x + 1 is computed byY ← XY ← Y+1,n(x) is computed by the empty program, anduin(x1, …, xn) is computed byY ← Xi ■
February 21, 2019
Theory of Computation Lecture 6: Primitive Recursive Functions I
11
PRC Classes
Definition:A function is called primitive recursive if it can be obtained from the initial functions by a finite number of applications of composition and recursion.Obviously, it follows that:Corollary 3.2:The class of primitive recursive functions is a PRC class.Furthermore, we have:Theorem 3.3:A function is primitive recursive if and only if it belongs to every PRC class.
February 21, 2019
Theory of Computation Lecture 6: Primitive Recursive Functions I
12
PRC Classes
Proof:Part I:If a function belongs to every PRC class, then, by Corollary 3.2, it belongs to the class of primitive recursive functions.Part II:Let f be a primitive recursive function and letCbe some PRC class. We want to show that f belongs toC.Since f is a primitive recursive function, there is a listf1, f2, …, fnof functions such that fn= f and each fiin the list is eitheraninitial functionorcan be obtained from preceeding functions in thelist bycompositionorrecursion.
February 21, 2019
Theory of Computation Lecture 6: Primitive Recursive Functions I
13
PRC Classes
Obviously, the initial functions belong to the PRC classC.Applying composition or recursion to functions inCresults in another function belonging toC.Thus each function in the list f1, …, fnbelongs toC.Since fn= f, f belongs toC. ■Corollary 3.4:Every primitive recursive function is computable.Proof:By the theorem just proved, every primitive recursive function belongs to the PRC class of computable functions.
February 21, 2019
Theory of Computation Lecture 6: Primitive Recursive Functions I
14
Another Word on PRC Classes
A class of total functionsCis called a PRC class ifthe initial functions n, s, and u belong toCanda function obtained from functions belonging toCbyrecursion or composition also belongs toC.Notice that this definition doesnotdemand allfunctions inCto be obtained from n, s, and u byrecursion or composition.There could beother functionsinC, say p and q, thatcannot be obtained from n, s, and u. According to thedefinition,Cis then still a PRC class if all functionsobtained from n, s, u, p, and q by recursion or compositionare also inC.
February 21, 2019
Theory of Computation Lecture 6: Primitive Recursive Functions I
15
Another Word on PRC Classes
Now look at the definition of primitive recursive functions:A function is called primitive recursive if it can be obtained from the initial functions by a finite number of applications of composition and recursion.So hereno additional functionssuch as p and q are allowed – all primitive recursive functions can be obtained from n, s, and u.Therefore, the class of primitive recursive functions is theminimalPRC class. All primitive recursive functions are contained in every PRC class. However, PRC classes can contain additional functions (see previous slide).
0
Embed
Upload