Popular in Course
Popular in Computer Information Technology
verified elite notetaker
This 23 page Class Notes was uploaded by Kathleen Cartwright on Monday September 28, 2015. The Class Notes belongs to CIS511 at University of Pennsylvania taught by J.Gallier in Fall. Since its upload, it has received 26 views. For similar materials see /class/215368/cis511-university-of-pennsylvania in Computer Information Technology at University of Pennsylvania.
Reviews for THEORYOFCOMPUTATION
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/28/15
46 THE PRIMITIVE RECURSIVE FUNCTIONS 309 46 The Primitive Recursive Functions The class of primitive recursive functions is de ned in terms of base functions and closure operations De nition 461 Let 2 a1 aN The base functions over 2 are the following functions 1 The emse function E de ned such that e for all w E 2 2 For every j l S j S N the j successor function Sj7 de ned such that 3110 waj for all w E 2 3 The projection functions Pi de ned such that DZ 101 wn wi for every n 2 1 every i l S i S n and for all 101710n E 2 Note that Pl1 is the identity function on 2 Projection functions can be used to permute the arguments of another function 310 CHAPTER 4 RAM PROGRAMS TUBING MACHINES A crucial closure operation is extended composition De nition 462 Let E a1 aN For any function 922 gtltgtltE gtE z and any m functions biz gtlt gtltE gtE 1 TL the composition of g and the h2 is the function f2gtltgtltE gtE denoted as g o h hm such that fw1wn gh1w1wnhmw1wn for all w17wn E 2 As an example f g 0 P2271312 is such that 100017102 9w27w1 46 THE PRIMITIVE RECURSIVE FUNCTIONS 311 Another crucial closure operation is primitive recursion De nition 463 Let E a1 aN For any function 922 gtltgtltE gtE mil Where m 2 2 and any N functions hi22 gtlt gtltE gtE m1 the function 192 x gtltE gtE t is de ned by primitive recursion from g and h hN if flt 7w27 7wm gw27 7wm7 fua17w27 7wm h1u7fu7w27 7wm7w27 7wm7 fuaN7w27 7wm hNu7fu7w27 7wm7w27 7wm7 for all u7w27wm E 2 312 CHAPTER 4 RAM PROGRAMS TUBING MACHINES When m l for some xed w E 2 we have f 107 nal h1u7fu7 fWN hNW u for all u E 2 For numerical functions ie when E a1 the scheme of primitive recur sion is simpler flt07m27uwxmgt gx27 7xm7 fx17m27 7xm hlx7fx7m27 u7mm7x27 7mm7 for all 050527xm E N 46 THE PRIMITIVE RECURSIVE FUNCTIONS 313 The successor function S is the function 31 75 1 Addition multiplication exponentiation and super exponentiation can be de ned by primitive recursion as follows being a bit loose we should use some projections add071 71 add711 171 Sadd71171 mult071 0 multm 171 addmultm7171 rexp0711 1 rexp711 171 mult7 expm7171 expm 71 Temp 0 13221312 supexp071 1 supexpm 1 71 6751901 supexpm 314 CHAPTER 4 RAM PROGRAMS TUBING MACHINES As an example over a b the following function g 2 x 2 gt 2 is de ned by primitive recursion 96711 1311007 9uai7v Si O P ugu7v7v7 Where l S 139 S N It is easily veri ed that guv vu Then f g 0 computes the concatenation function ie fuv uv 46 THE PRIMITIVE RECURSIVE FUNCTIONS 315 De nition 464 Let E a1aN The class of primitive recursive functions is the smallest class of functions over 2 which contains the base functions and is closed under composition and primitive recursion We leave as an exercise to show that every primitive recursive function is a total function The class of primitive recursive functions may not seem very big but it contains all the total functions that we would ever want to compute Although it is rather tedious to prove the following theorem can be shown 316 CHAPTER 4 RAM PROGRAMS TUBING MACHINES Theorem 465 For an alphabet E a1 aN euery primitive recursiue function is Turing computable The best way to prove the above theorem is to use the computation model of RAM programs Indeed it was shown in Theorem 441 that every Turing machine can simulate a RAM program It is also rather easy to show that the primitive recursive functions are RAM computable 46 THE PRIMITIVE RECURSIVE FUNCTIONS 317 In order to de ne new functions it is also useful to use predicates De nition 466 An n ary predicate P over 2 is any subset of We write that a tuple 0517xn satis es P as 0517xn E P or as Px1 70571 The characteristic function of a predicate P is the function Op 2 gt a1 de ned by Cp177mn 01 l P177xn 6 iff not Px1xn A predicate P is primitive recursive iff its characteristic function C p is prirn itive recursive We leave to the reader the obvious adaptation of the the notion of primitive recursive predicate to functions de ned over N In this case 0 plays the role of e and 1 plays the role of a1 318 CHAPTER 4 RAM PROGRAMS TUBING MACHINES It is easily shown that if P and Q are primitive recursive predicates over 27 then P Q P Q and P are also primitive recursive As an exercise the reader may want to prove that the predicate de ned over N primen iff n is a prime number is a primitive recursive predicate For any xed k 2 l the function ordk n exponent of the kth prime in the prime factorization of n is a primitive recursive function We can also de ne functions by cases 46 THE PRIMITIVE RECURSIVE FUNCTIONS 319 Lemma 467 If 1317 Pn are pairwise disjoint primitive recursive pred icates which means that B Q Pj for all i y j and f17fn1 are primitive recursive functions the function 9 de ned below is also primitive recursive f1 E W 1315 97 W in PM an otherwise writing T for x17 It is also useful to have bounded quanti cation and bounded minimization 320 CHAPTER 4 RAM PROGRAMS TUBING MACHINES De nition 468 If P is an n1 ary predicate then the bounded existential predicate Ely05Py holds iff some pre x y of 05 makes Py true The bounded universal predicate VyxPy holds iff every pre x y of 05 makes Py true Lemma 469 If P is an n 1 ary primitive recursive predicate then EIyxPy and VyxPy are also primitive recursive predicates As an application we can show that the equality predicate u v is prim itive recursive 46 THE PRIMITIVE RECURSIVE FUNCTIONS 321 De nition 4610 If P is an n l ary predicate then the bounded mini mization ofP min yx Py E is the function de ned such that min yx Py E is the shortest pre x of x such that Py7 if such a 3 exists xal otherwise The bounded maximization of P max yx Py E is the function de ned such that max yxPyE is the longest pre x of x such that Py if such a 3 exists xal otherwise Lemma 4611 If P is an n l ary primitive recursiue predicate then min yxPy and max yx Py are primitive recursiue functions So far the primitive recursive functions do not yield all the Turing computable functions In order to get a larger class of functions we need the closure op eration known as minimization 322 CHAPTER 4 RAM PROGRAMS TUBING MACHINES 47 The Partial Recursive Functions The operation of minimization sometimes called minimalization is de ned as follows De nition 471 Let E a1 aN For any function 922 gtltgtltE gtE ml Where m 2 0 for every j 1 S j S N the function 192 x gtltE gtE is de ned by minimization over aj from 9 if the following conditions hold for all w17wm E 2 1 fw1 wm is de ned iff there is some n 2 0 such that ga w1 wm is de ned for all p 0 S p S n and 9agl7wl7 u7wm 6 47 THE PARTIAL RECURSIVE FUNCTIONS 323 2 When fw1 wm is de ned fw1wm a Where n is such that 90 7w17 7wm and 9ag7w17 7wm 7g 6 foreveryp0 p n 1 We also write fw1 wm mmjuguw1 wm e 324 CHAPTER 4 RAM PROGRAMS TUBING MACHINES Note When fw1 wm is de ned fw1wm a7 Where n is the smallest integer such that condition 1 holds It is very important to require that all the values ga w1 wm be de ned for all p 0 S p S 11 when de ning fw1wm Failure to do so allows non computable functions Minimization can be Viewed as an abstract version of a While loop 47 THE PARTIAL RECURSIVE FUNCTIONS u z 6 While guw1 wm y e do u uaj endwhile let fw1wm u Remark Kleene used the u notation fltwl7 7wm lu julgu7wl7 actually its numerical form fltxl7uwmmgt IU xgx7x17quot 7mm0l7 325 326 CHAPTER 4 RAM PROGRAMS TUBING MACHINES The class of partial computable functions is de ned as follows De nition 472 Let E a1 aN The class of partial recursive func tions is the smallest class of functions over 2 which contains the base functions and is closed under composition primitive recursion and mini mization The class of recursive functions is the subset of the class of partial recursive functions consisting of functions de ned for every input 47 THE PARTIAL RECURSIVE FUNCTIONS 327 One of the major results of computability theory is the following theorem Theorem 473 For an alphabet E a1 aN every partial recursive function is Turing computable Conversely every Turing computable func tion is a partial recursive function Similarly the class of recursive functions is equal to the class of Turing computable functions that halt in a proper D for every input To prove that every partial recursive function is indeed Turing computable since by Theorem 441 every Turing machine can simulate a RAM program the simplest thing to do is to show that every partial recursive function is RAM computable 328 CHAPTER 4 RAM PROGRAMS TUBING MACHINES For the converse one can show that given a Turing machine there is a prim itive recursive function describing how to go from one ID to the next Then minimization is used to guess whether a computation halts The proof shows that every partial recursive function needs minimization at most once The characterization of the recursive functions in terms of TM s follows easily There are recursive functions that are not primitive recursive Such an ex ample is given by Ackermann s function 47 THE PARTIAL RECURSIVE FUNCTIONS 329 Ackermann s function A recursive function which is not primitive recursive A y y 1 Ax 1 0 Ax1 Ax 1 y 1 Ax Ax 1y It can be shown that A0 x x 1 A1 x x 2 A2 x 2x 3 A3 x 2 3 and with A4 0 16 3 13 330 CHAPTER 4 RAM PROGRAMS TUBING MACHINES For example A4 1 216 3 1442 2215 3 Actually it is not so obvious that A is a total function This can be shown by induction using the lexicographic ordering j on N x N which is de ned as follows mm j mh iff either mm andnn or m lt m or mmandnltnl We write mm lt m when m7n j m and mm y m We prove that Am n is de ned for all m n E N x N by complete induction over the lexicographic ordering on N x N
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'