Class Note for CMPSCI 601 at UMass(34)
Class Note for CMPSCI 601 at UMass(34)
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 13 views.
Reviews for Class Note for CMPSCI 601 at UMass(34)
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 7 Theorem 94 The busy beaver function 0n is even tually larger than any total recursive function Theorem 95 There is a Universal Turing Machine U such that Theorem 96 Unsolvability of Halting Problem Let HALT Pn m 1 TM eventually halts Then HALT is re but not recursive Listing of all re sets W0 W1 W2 W in 1 Mil 1 Corollary 98 Let K in Mnn1 in UPnan 1 n I n E Wn Then K E re Recursive Notation Mna means that TM Mn converges on in put 33 ie Mnai gt MnaEN gt Fundamental Theorem of re Sets Let S g N TFAE 1 S is the domain of a partial recursive function ie 3W5 d0mMn39 93 EN 1 Mn93i 2 S Z or S is the range of a total recursive function ie S Z or S rangeMn MAN for some total recursive function 3 S is the range of a partial recursive function ie S MAN for somen E N 4 S is re ie S W for some n E N Proof Please learn this proof 1 gt 2 Assume 1 S 2 I case 1 S Z Thus 5 satis es 2 case 2 5 Z let a0 6 S From Mn compute MT which on input z does the follow ing 1 a Lz 31 Rz ie z Pay 2 run for y steps 3 if it halts then returna 4 else returna0 Claim 5 MAN I a E N MTltNgt g s MAN 2 5 Suppose a E 5 Thus converges in some number y of steps Therefore MTP1 13 Note the noncomputable step in the construction there is no way to tell whether we are in case 1 or case 2 2 gt 3 Assume 2 HS 2 thhen S M0N where M0 is a Turing machine that halts on no inputs Otherwise S MAN ie S is the range of the partial recursive function Note Even though is total it is still considered a partial recursive function However of course is not strictly partial 3 gt 4 Assume 3 S From Mn we construct Md which on input a does the following 1 fori ltooo 2 run MAO Mn1 for 239 steps each 3 if any of these output 13 then returnl The above construction is called dovetailing Claim Md p5 Ifa E S then a E rangeMn So for some 339 and k Mnj a and the computation takes k steps Thus at round 239 maxj k Mda will halt and output 177I If a e S then Mda will never halt ThusS Wd 2 13 I Mda l 4 gt 1 Assume 4 and thus 5 W S 2 i Z 1 From Mn construct Md which on input a does the fol lowing 1 run 2 if 1 then return1 3 else run forever 5 93 I Md93i ThusS domMd 2 I Mda Q This theorem lets us put the enumerable in re A nonempty language A is said to be Turing enumer able if there exists a TM that when started on blank tape lists the elements of A The TM will take forever to do so if A is in nite and it might repeat elements It should be pretty clear that for nonempty sets Turing enumerable means exactly the range of a total recursive function So except for Z Turing enumerable means exactly re An in nite set of numbers is Turing enumerable m m creasmg order if it is Turing enumerable by a machine that lists 239 before 339 wheneverz39 lt 339 It s pretty easy to see that an in nite set is Turing enu merable in increasing order iff it is recursive 0 gt Keep running the TM until you hit the target or pass it 0 Run through all numbers in increasing order and test each one listing the ones that are in the language CMPSCI 601 Reductions Lecture 7 De nition 71 Let S and T be sets of numbers We say that S is reducible to T S g T iff there exists a total recursive f N gt N such that V w E N w E S gt E T Q Note Later we will require f E FDSPACElog The notation S g T is meant to suggest S is no more di icult than T To use this notation we should be con dent that g is re exive and transitive You ll check this on HW3 The notation suggests as well that it is antisymmetric but it is not It is quite possible to have 5 g T T g S and S 7 T all be simultaneously true In this case we say 5 and T are equivalent This kind of reduction is called a manyone reduction Later we ll see another kind called a Turing reduction An Example Arm 2 in i Mn017 Claim K S A037 Proof De ne f as follows erase input if 1 then write 17 M n write n Mn else loop Tl E K gt 1 gt Z gt E A0317 Q If K 3 A0 really means K is no harder than A047 or equivalently A047 is no easier than K then we should be able to conclude that A047 is not recursive because K is not recursive The next theorem will let us do this in general 10 Fundamental Theorem of Reductions If S g T are languages then 1 HT is re then S is re 2 HT is core then S is core 3 If T is Recursive then S is Recursive Moral Suppose S g T Then 0 HT is easy then so is S HE is hard then so is T Another way to phrase this is that re core and Recursive are each downward closed under reductions 11 Proof Let f S g T ie E S gt fa E T 1 Suppose T W 2 I 1 From Mi compute the TM My which on input a does the following a compute f b run Mifa My f Mi Then 65 ltgt x ET ltgtMzf33 1 ltgt M Iw1i Therefore 5 Wit and we have shown that S E re as desired 12 Recall our hypothesis for this proof f S g T ie E S gt fa E T The last two parts of the theorem follow directly from the rst 2 Observation 5 g T gt 3 g T T E core gt T E re E re gt S E core 3 T E Recursive gt T E re T E core gt S E re S E core gt S E Recursive l3 De nition 72 Let C lt N C is recomplete iff l C E re and 2 VA 6 re A g C Intuition C is a hardest re set In the g ordering in that it is above all other re sets Q If you have seen a de nition of NPcomplete this def inition should look familiar NPcompleteness was ex plicitly modeled on this historically earlier concept It is perhaps odd that there are any recomplete sets at all the de nition doesn t suggest why there should be But in fact we ve already seen one 14 Theorem 73 K is 716 complete Proof Let A E re be arbitrary so we know that A 2 W6 for some 239 We want E A gt fn E K Note the implicit types here The number f is going to be interpreted as the number of a TM De ne the recursive function f which on input n com putes this particular TM M n Erase input Write n Mi n E A gt 1 gt V23Mfna 1 ltgt Mfnfn 1 ltgt N E K Q Get used to numbers being treated as machines Lots of our standard languages are of the form n Mn is a TM such that 15 Proposition 74 Suppose that C is icecomplete and the following hold I S E re and 2 C 3 S then S is 1 16 complete Proof Show VA 6 reA g 5 Know VA 6 reA g C Follows by transitivity of g A g C 3 S Q Corollary 75 A0317 is icecomplete Every icecomplete set is 1 16 and hot recursive 16 HALT Pn m 1 TM eventually halts Proposition 76 HALT is Icecomplete Proof We have already seen that HALT is re It thus suf ces to show that K g HALT We want to build a total recursive f such that for all 10 E N w E K gt fw E HALT Mwwl gt MLfwRfwhalts That is we want 1 gt MAT halts where fw P r Given 10 let M aw Erase input Write 111 M w igl e igellgg Letting f PE39w 0 we have that 1 gt Mgw0 halts gt fw E HALTQ l7 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'