Class Note for CMPSCI 601 at UMass(48)
Class Note for CMPSCI 601 at UMass(48)
Popular in Course
Popular in Department
This 15 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 13 views.
Reviews for Class Note for CMPSCI 601 at UMass(48)
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 8 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 CMPSCI 601 Reductions Lecture 8 Def 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 Theorem 81 Let A be a set other than 7 or N such that if Mi and M j are equivalent machines 239 and j are either both in A or both not in A Then A is not recursive Proof Suppose that the numbers of machines that never halt are not in A What if they aren t See HW3 Since A is nonempty pick a number If so that M g E 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 Q CMPSCI 601 Primitive Recursive Functions Lecture 8 On HW2 we de ned the programming language Bloop with integer variables and bounded loops It turns out that the class of functions om N to N that are implementable in Bloop is 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 We ll eventually see the de nition of general recursive functions that is equiva lent to Turing machines But rst we ll give the de nition of a less power il kind of recursion It de nes functions that are guaranteed to halt but can t de ne all total recur sive functions On HW3 we ll prove that there are recursive functions that are not primitive recursive and that the primitive recursive mctions are exactly those implementable in Bloop 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 82 The primitive recursive functions PrimRechns is the smallest class of functions con taining the Initial functions and closed under Composi tion and Primitive Recursion Q Proposition 83 T he following are m PrimRechns I M1x if x gt 0 then x 1 else 0 2 2393 ify xthenx y elseO 3 4 17 5 expww y 6 expx if a 0 then 1 else 2explt1gt expx 22 Godel discovered that you can code sequences in PrimRechns which he did using number theory Proposition 84 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 ut g x 1 1L t gt 1 Primet PrimeF0 2 PrimeFx 1 NextPrimePrimeFx Proposition 85 IsSeq Length Item 6 PrimRechns where Seqa0 a1 an 2 2ao13al1 PrimeFn 1 IsSeqS if S is a Sequence number 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 GoodxS ItemS uy lt S IsSeqS PrimeFiy1S PrimeFiy2 5 Q As your intuition about Bloop should begin to tell you and your work on HW3 should con rm we can do al most anything with primitive recursive functions 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 SeqID0 ID1 IDt Where each ID is a sequence number of tapecell con tents Seqogt7a17 39 39 val 17 i0ai7ai1 39 39 39 a r COMPn x c y E STARTItemc 0 8 ENDItemc Lengthc 1 y Vi lt LengthcNEXTn Itemc 239 Itemci 1 Q 10 Theorem 86 T he following problems are decidable in polynomial time EmptyNFA N Nis an NFA N 2DFA D DisaDFA 131 2 MemberNFA ltNw Nis anNFA w E N EqualDFA D1D2 D1D2 DFAS D1 D2 EmptyCFL G G isaCFG 30 9 MemberCFL ltGw GisaCFG w 6 130 11 EmptyNFA H W4 2DFA D 1 DisaDFA 131 2 D E 2DFA 42gt E E EmptyNFA MemberNFA ltNw Nis an NFA w E N V 01 12 EqualDFA Z ltD1 D2 1 Z D1 D2 6 EqualDFA 42gt E 1 D2 U D1 0 g 6 EmptyNFA EmptyCFL H W3 13 MemberCFL ltGw GisaCFG w 6 130 CYK Dynamic Programming Algorithm 1 Assume G in Chomsky Normal Form N gt AB N gt a 2 Input w wlwgwn G with nonterminals SAB 0 otherwise 4 returnSln 3 Nij E N if N gt wi E R then 1 else 0 NM 2 V Elkz39 g k lt j AM 13km N gt AB ER 14 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 15
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'