Class Note for CMPSCI 601 at UMass(14)
Class Note for CMPSCI 601 at UMass(14)
Popular in Course
Popular in Department
This 18 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 24 views.
Reviews for Class Note for CMPSCI 601 at UMass(14)
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: 02/06/15
CMPSCI 601 Recall From Last Time Lecture 11 De nition We say that S is reducible to T S g T iff 3 total recursive f N gt N Vw e N w e S ltgt fw e T In the future we will insist that f E FL Theorem Suppose S g T Then 1 HT is re then Sis re 2 HT is core then S is core 3 If T is Recursive then S is Recursive De nition C is recomplete iff 1 C E re and 2 VA 6 re A g 0 Theorem K HALT and A047 are re complete hence not recursive CMPSCI 601 Reductions Lecture 11 De nition We say that S is reducible to T S g T iff f 6 FL Vw e N w e S ltgt fw e T Intuition S g T iff the placement of a very simple front end f before a Trecognizer creates an Srecognizer X5 xTof 16 VXsxXTfx The Reduction Game To build a reduction f from S to T you must solve the following puzzle For each input w what membership question f 20 can I ask T such that the answer is the membership ques tion to S RiceMyhill Shapiro Theorem Our proof that A047 was recomplete had little to do With the numbers 0 or 17 A very similar argument can be used to show that any nontrivial property of Turing machines is undecidable See P Theorem 32 page 62 De nition 111 Two Turing machines M and N are equivalent if for any input 2 M x iff N 201 and if both output strings M and N are de ned they are equal A De nition 112 A language is a property of machines if for any numbers 239 and 339 such that M and M j are equiv alent machines 239 and j are either both in A or both not in A 4 Theorem 113 Let A be a language other than 7 or N that is a property of machines Then A is not recursive Proof Suppose that the numbers of machines that never halt are not in A If they aren t we replace A by A and prove that the latter is not recursive Since A is nonempty pick some number If so that Mg 6 A We will reduce K to A which means we must de ne a total recursive function f so that n E K iff fn E A This means that for any machine Mn we must build a machine M n that will have the property necessary for A iff Mn accepts n We ll do this using our assumptions If Mn accepts n M n will be equivalent to M g and thus f will be in A If Mn does not accept n M n will never halt and thus f will not be in A This is easy We design M n so that it rst runs Mn on n then if it nishes that job runs Mg on the original input This machine simulates Mg if Mn accepts n and never halts otherwise Since K g A A cannot be recursive We cannot say that A is recomplete because it might not be re in fact most such A s are not A CMPSCI 601 Primitive Recursive Functions Lecture 11 In Lecture 1 and HWl we de ned the programming lan guage Bloop with integer variables and bounded loops We will now see that the class of functions om N to N that are implementable in Bloop are a very well studied class called the primitive recursive functions You may have wondered whether recursion as you know it from programming has anything to do with recursive functions in this course The name indeed comes om de ning functions recursively Later this lecture we ll de ne the general recursive functions that are the same as the partial recursive functions But rst we de ne a less powerful kind of recursion It de nes functions that are guaranteed to halt but can t de ne all total recursive functions On HW4 we ll prove that there are recursive functions that are not primitive recursive So the primitive recur sive functions are a proper subset of the total recursive functions Initial functions 00 0xx1 7rx1xnxi n12 1 i n Composition 9 N gt N1 i m h Nm gt N Chiglaagmxlanaive hglT7quot39agmT Primitive Recursion g N gt N h N gt N n 2J1 m 739 Wm 41 yk given by f0y1yk 9ylyk Z hfnay17quot397yk7nay17quot397yk De nition 114 The primitive recursive functions PrimRechns are the smallest class of functions con taining the Initial functions and closed under Composi tion and Primitive Recursion A Proposition 115 T he following are in PrimRechns I M1x if x gt 0 then x 1 else 0 2 2393 ify xthenx y elseO 3 4 17 5 expmy y 6 expx if a 0 then 1 else 2explt1gt 2 expx 22 Proposition 116 The class PrimRechns is closed un der the bounded noperator If f is a pr function then nc lt y 0 is de ned to be the least a such that 0 ifsuch an 2 exists with a lt y or to be 3 otherwise On HW3 you are asked to relate pr functions in the form of Bloop functions to Turing machines A key tool in doing this is the coding of sequences of numbers as single numbers rst developed by Godel He began with elementary number theory Proposition 117 Prime PrimeF E PrimRechns where Primex if x isprime then 1 else 0 PrimeFn prime number n ie PrimeF0 2 PrimeF1 3 PrimeF2 5 PrimeF3 7 PrimeF4 11 Proof 3513 32 S yxz y Primex 1 gt1 Vy lt gt 3 1 NextPrimex Mt g x11 1 tgt a Primet PrimeF0 2 PrimeFx 1 NextPrimePrimeFx Proposition 118 IsSeq Length Item 6 PrimRechns where Seqa0 a1 an 2 2ao13al1 PrimeFn 1 IsSeqS if S codes a Sequence then 1 else 0 LengthSeqa0a1 an 2 n1 ItemSeqa0 a1 an Li Proof GoodxS Vy lt lt 1 PrimeFyS V y 2 1 PrimeFy IsSeqS 3x lt SGoodxS LengthS ux lt S G00dxS ItemS uy lt S IsSeqS PrimeFiy1S PrimeFiy2 5 A As your intuition about Bloop should begin to tell you almost anything computable can be computed in Bloop On HW4 you ll nd a tr function that can t In par ticular we can simulate Turing machines Primitive Recursive COMP Theorem Kleene Let COMPn 13 c 3 mean y and that c is Mn s complete computation on input 2 Then COMP is a Primitive Recursive predicate Proof We will encode TM computations c SeqID0ID1 IDt Where each IDi is a sequence number of tapecell con tents Seqogt7a17 3970 5 17i0 7a ii a iJr1quot 39 quot017 COMPn x c y E STARTItemcO 1 ENDItemcLengthc 1y Vi lt LengthcNEXTn Itemc 239 Itemci 1 Q 10 CMPSCI 601 Primitive Recursive Bloop Lecture 11 We have two sets of functions from N to N each de ned recursively 0 CO 0x and 7rz1xn are pr 0 the composition of pr functions is pr and 0 the function made from two pr functions by the primitive recursion rule is pr 0 statements are Bloop program blocks 0 an assignment of a callbyvalue function call is a block 0 the concatenation of two blocks is a block 0 a variablebounded loop containing a block is a block To be more precise about Bloop we would have to be more careful about a formal semantics Esssentially given a binding of some variables at the start of a block we get a new binding at the end and the exact transformation of the binding could be de ned by induction Here we ll rely on our intuitions about real programs 11 Theorem 119 Every primitive recursive function can be implemented in Bloop Proo Base Cases declare zeta return x declare sigmax return x declare pi24 x1 x2 x3 x4 return x2 12 Composition Example fxa 9h1x7 y h2x7 y h3x7 Primitive Recursion Example f0yz gyz 1 y Z y z n y declare fnyz a gyz i zeta for n a haiyz i return a 13 Theorem 1110 The output of any Bloop program is a primitive recursive function What is easier to prove by induction is the following Theorem 1111 After any Bloop program block any vari able de ned at the end is a primitive recursive function of those variables de ned at the beginning Proof Successor If the block is xi and the variables de ned are 21 xn then the end value of xj for j 239 is 7rx1xn and the end value of xi is 07rx1 xn Assignment Ifthe block is x f yl yk then by the 1H since f is de ned elsewhere it is a pr func tion of the y s By projections we can make 1 a pr function of all de ned variables and other variables are unchanged 14 Concatenation If the block is B C where B and C are blocks by the 1H every variable 3 de ned after B is a pr function of those variables as de ned be fore B and every variable z de ned after 0 is a pr function of the y s By composition we write each z as a pr function of the x s Loops Suppose the block is for I1 B where B is a block and let us rst consider the case where only one variable y is de ned during B By the 1H the effect of B on y is given by a pr function We de ne f 72 go to be the value of 3 after B has been executed n times starting from y 2 yo Clearly we can de ne f by primitive recursion with gy0 90 and hfn7 yo 7 yo blflquot 90 Now say we have k different variables de ned during B We use the sequence tools developed above Let C be a block that takes its single argument decodes it into k variables runs B on them and codes the k an swers as a single number By composition C s effect on its variable is pr and by the argument above so is that of for x C Encoding and decoding gives us pr functions for for x B A 15 CMPSCI 601 General Recursive Functions Lecture 11 We will now increase the power of the primitive recursive functions by adding one more rule De nition 1112 If fxy1 yk is a function we de ne the uoperator on f with respect to x ux fzy1 is the following partial function gy1 Ifthere is a value ofx such that 1 lt y and fx yl 0 then gy1 is the least such value If there is no such value of 13 gy1 yk is unde ned A De nition 1113 The general recursive functions are the least set of partial functions containing the initial func tions and closed under composition and the u operator A De nition 1114 Floop is the programming language consisting of Bloop augmented with one more statement type If B is a block possibly changing the value of 13 while x B is a block that keeps executing B as long as 1 is positive It may run forever if so its be havior is a strictly partial function A 16 Theorem 1115 A partial function from N to N is gen eral recursive i ii is computed by a Floop program Proof Exercise HW4 4 Theorem 1116 A partial function from N to N is general recursive i ii is partial recursive Proof 0 gt Inductively simulate Floop blocks by TM s 0 lt Let f be apartial recursive function Then f 3 iff there is a halting computation of f s TM on in put z yielding 3 Using the COMP predicate and the u operator we construct a general recursive function that outputs f if it is de ned A 17 mm Arlthmetlc H1erarchy W c0re Recursive 139 e re complete Primitive Recursive EXPTIME PSPACE c0NP PolynomialTime Hierarchy complete c0NP NP NP 1 c0NP NP complete quottruly feasiblequot NC NC2 logCFL SAC NSPACE log n 3 DSPACE log n Regular LogarithmicTime Hierarchy 18
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'