Class Note for CMPSCI 601 at UMass(44)
Class Note for CMPSCI 601 at UMass(44)
Popular in Course
Popular in Department
This 13 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 16 views.
Reviews for Class Note for CMPSCI 601 at UMass(44)
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 6 Def DTIME NTIME DSPACE measured on Multi tape Turing Machines Th DTIMEtn g RAMTIMEtn g DTIMEtn3 L E DSPACE10gn P E DTIMEWW E lDTIMEmz NP 3 NTIMEMOW E ENTIMEM PSPACE z DSPACEn0lt1gt DSPACEW39 2 1 Th For tn 2 n 2 log n DTIMEtn g NTIMEtn g DSPACEtn DSPACEsn g DTIME20ltSlt gtgt Cor L 0 P C NP Q PSPACE CMPSCI 601 Busy Beaver Function Lecture 6 De nition 61 The busy beaver function 0n is the max imum number of one s that an 71 state TM with alphabet E 0 1 can leave on its tape and halt when started on the all 0 tape To t our de nitions note that O is now the blank character A Note that C71 is well de ned There are only nitely many nstate TMs with E 0 1 Some nite subset Fm of these eventually halt on input 0 Some element of Fn prints the max of 1 s 0n ee 17117 11 00 a 071 22 00 a 1 011 h 01 0 0 00 1 1 000 0 0 1 11000 11000 1 1 1 1 1 1 1 0amp00000 0100000 010m000 0101000 0 0111000 1 1111000 1 1111 1111000 1111 1 1111110 1111110 Q1 Q2 Q3 Q3 Q3 Q1 Q2 Q2 Q2 Q2 Q3 Q3 Q3 Q1 h How quickly does C71 grow as 71 gets large Is C71 E 0012 0073 02quot 001 022 0ltexpltngtgt CMPSCI 601 Some Values of 0 Lecture 6 States Max of 1 s Lower Bound for C71 3 03 6 4 04 13 5 05 2 4098 6 06 gt 10865 See the web pages of Penousal Machado eden dei uc pt and Heiner Marxen www drb insel de he ine rBB for more on this problem and its variants Theorem 62 Let f N gt N be a total recursive func tion New I 0 That is fn 00n Proof Note lim 0 n MX 96 We will Show for all suf ciently large n 071 2 901 gn is computed by a kstate TM for some Is For any 11 de ne the TM bina 0n 2 print n compute g to ungy log n k 17 0 has log n k 17 states 0 prints gn 1 s Once n is big enough that n 2 log n k 17 C71 2 a logni k17 2 901 CMPSCI 601 A Pairing Function Lecture 6 On HW2 we de ne a pairing function PNXNN onto We can use the pairing function to think of a natural num ber as a pair of natural numbers Thus the input to a Turing machine is a single binary string which may be thought of as a natural number a pair of natural numbers a triple of natural numbers and so forth Later we will worry about the complexity of the pairing and stringconversion functions do you think they are in L CMPSCI 601 Numbering Turing Machines Lecture 6 Turing machines can be encoded as character strings which can be encoded as binary strings which can be encoded as natural numbers TM 1 2 3 4 O 10 gt 3LJ gt 00 00 l 11 gt 4LJ gt 01 01 LJ 2LJlt 0LJ 10lt 11lt 1gt 1Igt gt OIgt 0Igt OIgt ASCII 10 gt11 gt2LJlt 1Igt gt OIgt 01 20 N 11 There is a simple countable listing of all TM s M0 M1 M2 CMPSCI 601 The Universal Turing Machine Lecture 6 Theorem 63 There is a Universal Turing Machine U such that WWW MW Proof Given mm compute n and m n is a binary string encoding the state table of TM Mn We can simu late Mn on input m by keeping track of its state its tape and looking at its state table 11 at each simulated step A Let s look at LU the set of numbers P n m such that the Turing machine Mn eventually halts on input 71 We ll call this language HALT The existence of U proves that HALT is re and we ll now show it s not recursive 10 HALT Pnm TM eventually halts Theorem 64 Unsolvability of the Halting Problem HALT is 1 16 but not recursive Proof HALT w U eventually halts w 1 Wm 1 U U erase tape printl Suppose HALT were recursive Then 0n would be a total recursive function Cycle through all nstate TMs Mi and if Pz39 0 e HALT then count the number of 1 s in Return the maximum of these But 0n isn 1 total recursive so we have a contradiction A ll Lecture 6 Listing All re Sets CMPSCI 601 The set of all re sets W0 W1 W2 Wm W0 W1 W2 W3 K F 80110 01 70101000E0 01 6011000l00 10 501010E000 01 40110E1000 01 3010l00100 10 201l001000 10 10l0101011 10 0M11010110 01 n012345678 12 CMPSCI 601 Diagonalization and Halting Lecture 6 K n Mnn1 n UPnan1 n newn Theorem 65 F13 7101716 Proof F n n g Wm Suppose F were re Then for some 0 F 2 WC 2 nMCn1 ceK lt2 Mcc1lt 061 lt2 06 Corollary 66 K e re Recursive 13
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'