Class Note for CMPSCI 601 at UMass(40)
Class Note for CMPSCI 601 at UMass(40)
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 20 views.
Reviews for Class Note for CMPSCI 601 at UMass(40)
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 12 Def The primitive recursive functions PrimRechns is the smallest class of functions containing the Initial functions and closed under Composition and Primitive Recursion Initial functions 00 acc1 7rc1cnm n12 1 i n Composition 9 N gt N1 i m h Nm gt N Chglgm1ck hgligmi Primitive Recursion g N gt N h N gt N fn111myk Ply Wm 91 9k given by f03919 yk 9yla ayk hfnayla 9ykanayla ayk Facts and Exercises 1 A function is primitive recursive iff it is computable in Bloop 2 Every primitive recursive function is total recursive 3 There is a total recursive function that is not primitive recursive 4 There are primitive recursive functions that encode and decode sequences of integers by single integers Using sequences primitive recursive functions are pow erful enough to talk about Turing machines Primitive Recursive COMP Theorem Kleene Let COMPn 27 031 mean y and that c is Mn s complete computation on input 27 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 IDZ Seqgtj a1 ai1 0 0239 ai19 90 7quot COMPn 27 C y E STARTItemc 0 27 ENDItemc Lengthc 1 y Vi lt LengthcNEXTn Itemc 239 Itemci 1 A De nition 121 The general recursive functions are the set of partial functions obtained by closing the initial functions under composition and the uoperator We de ne uc flf y 0 for an input 3 to be the least 2 such that f lf y 0 if one exists or otherwise unde ned Q Facts and Exercises 0 The general recursive functions are the closure of the pr functions under the uoperator 0 A partial function is general recursive iff it is com putable in Floop the language obtained from Bloop by adding a whi 1e statement 0 A partial function is general recursive iff it is partial recursive computable by some TM 0 A total function is partial recursive iff it is in DTIMEf for some primitive recursive function f Theorem 122 T he following problems are decidable in polynomial time EmptyNFA N I N is an NFA N 3 2DFA D I D isaDFA D 2 MemberNFA Nwgt N is an NFA w E N EqualDFA D1D2gt D1D2 DFAs D1 D2 EmptyCFL G I G isaCFG G 3 MemberCFL 0212 I GisaCFG w E G EmptyNFA N No start nal path in graph of N 2DFA D DisaDFA D 2 D E 2DFA 42gt b E EmptyNFA MemberNFA Nwgt Nis an NFA w E N Convert to another reachability problem V 01 EqualDFA 131132 I D1 D2 D1 D2gt E lt3 D2 U D1 E EmptyNFA EmptyCFL H W4 MemberCFL 0212 I GisaCFG w E G CYK Dynamic Programming Algorithm 1 Assume G in Chomsky Normal Form N gt AB N gt a 2 Input 21 wlwgwn G with nonterminals SAB 0 otherwise 4 return51n 3 NM E NM if N gt wi E R then 1 else 0 Nig Z V S k ltj Bk1 j N gt AB ER CMPSCI 601 Today s Main Theorem Lecture 12 Theorem 123 T he following problem is canecomplete 2CFL G I G is a CFG G Proof J Hartmanis Neil s advisor 2CFL E ne Input G De ne 2 mm11212122 l forz39 2 0tooo 2 if 212239 1 G then returnl We use the the CYK algorithm for each MemberCFL check Clearly this returns 1 iff G E 2CFL Proposition 124 EMPTY ts c0re complete where EMPTY n I Wn 3 Proof Show NONEMPTY to be recomp1ete Show it re and reduce K to it Good practice Q Claim 125 EMPTY g 2CFL Corollary 126 2CFL ts c0re complete and thus not recursive How can we prove the Claim We need to de ne g N gt 01 nEEMPTY ltgt gn EECFL VMnfc1 ltgt gn332 Mn has no accepting computations 42gt gn 2 10 We need to represent entire computations of TM s by strings Assume that Mn is a onetape machine We rst de ned a string called an Instantaneous De scription or ID of a computation of Mn Mn has alphabet 0 1 states 0 l Q where f is the halting state and 1 is the start state IDO 1gtw1w2wru L 77 Suppose Mn in state l looking at a gt writes a gt changes to state 3 and moves to the right ID1 Z gt3w1w2wru In general the ID shows the tape up to and including the rst blank after the last nonblank with a character for the state inserted just left of the head position It is easy to tell whether a string is a valid ID 11 YesCompn t ID0ID ID2ID IDt I IDO IDt accep mg Note that IDO can have any string in 0 1 as the input string We write every other ID backwards to allow easy checking by a CFL Lemma 127 For each n YesCompn is a CFL Furthermore there is a function g E F L for all n gn codes a contextfree grammar and gn YesCompn En 01gtLI01jnwhereMnhasqn states comp of Mn n E EMPTY ltgt YesCompn 2 42gt gn E 2CFL n The grammar must generate every string that does not code an accepting computation of Mn 12 Proof YesCompn Un U An U Dn U Zn Un w E 2 I 21 not in form ID0IDt An w E 2 I 212 doesn t start with an initial ID of Mn Dn w E 2 I EliIDi1 doesn t follow from IDZv Zn w E 2 1 212 doesn t end withf gt 1U U n AM and Z are regular languages To be in Dn a string must contain a letter in IDiH that does not follow from the corresponding place in mi by the rules of Mn either the tape changes away from the head or changes the wrong way at the head A PDA could guess and verify the point at which this happens Q 13 Thus 9 EMPTY g 2CFL n E EMPTY 42gt YesCompn 2 42gt gn E 2CFL 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'