Class Note for CMPSCI 601 at UMass(2)
Class Note for CMPSCI 601 at UMass(2)
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 10 views.
Reviews for Class Note for CMPSCI 601 at UMass(2)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 02/06/15
CMPSCI 601 Recall From Last Time Lecture 9 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 NTIME and NP Lecture 9 NTIME E probs accepted by NTMs in time Otn NP 2 NTIMEn0lt1gt cNTIMEW i l Theorem 91 For any function DTIMEtn g NTIMEtn g DSPACEtn Proof The rst inclusion is obvious For the second note that in space Otn we can simulate all computa tions of length Otn so we will nd the shortest ac cepting one if it exists A Recall DSPACEtn g DTIME20lttltngtgt Corollary 92 L C P g NP g PSPACE So we can simulate NTM s by DTM s at the cost of an exponential increase in the running time It may be pos sible to improve this simulation though no essentially better one is known If the cost could be reduced to poly nomial we would have that P 2 NP There is probably such a quantitative difference between the power of NTM s and DTM s But note that qualita tively there is no difference If A is the language of some NTM N it must also be re because there is a DTM that searches through all computations of N on 11 rst of one step then of two steps and so on If 11 E A D will eventually nd an accepting computation If not it will search forever What about an NTMbased de nition of recursive or Turingdecidable sets This is less clear because NTM s don t decide they just have a range of possible actions But one can de ne a function computed by an NTM in a reasonable way and this leads to the same classes of partial recursive functions total recursive functions and recursive sets CMPSCI 601 Unsolvable Problems Lecture 9 We show that a particular language is recursive or re by exhibiting a Turing machine and showing that it decides or accepts the language Note that exhibiting means proving the existence of rather than giving a state ta ble for and we may use highlevel language to prove that existence We want to show that certain languages are not recursive or re which means showing that no possible Turing ma chine can decide or accept them The basic process will be to reduce an already unsolvable problem to the target problem showing the latter unsolv able But clearly we need to start somewhere by showing some problem to be unsolvable in some other way Later in this lecture we ll see the standard example of an unsolvable problem the halting problem of determin ing whether a given TM will halt on a given input But rst since many of you have seen the halting problem before we will show a different related problem to be unsolvable CMPSCI 601 Busy Beaver Function Lecture 9 De nition 93 Suppose we start an nstate TM with tape alphabet 0 1 on a tape with all zeroes We de ne the busy beaver function 001 to be the maximum number of ones left on the tape by any of the nstate TM s that halt in this situation Note that to t our de nitions 0 is now the blank character A Note that C71 is well de ned There are only nitely many nstate TMs with Z 2 0 1 Some nite subset Fm of these eventually halt on input 0 Some element of Fn prints the maximum number of 1 s on the tape and this number is 0n ee 17117 1 00 aa 0717 2 00 a 1 a 01111 03 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 oltexpltngtgt CMPSCI 601 Some Values of C71 Lecture 9 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 machado and Heiner Marxen WWW drb insel deNheinerBB for more on this problem and its variants Theorem 94 Let f N gt N be any total recursive function T hen Thatis 2 00n Proof Let you n Hgfm Note h Z 0 quot m 901 We will Show that for all suf ciently large n 071 2 901 First note that since f is total recursive and 9 depends on f in a simple way it is easy to design a TM that computes Let k be the number of states in this TM For any 11 de ne the TM On 2 print n compu te 9 tgl ggy Hog M 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 logn k17 2 901 10 CMPSCI 601 A Pairing Function Lecture 9 We have mentioned type casting of the input or output of Turing machines For example we want to think of numbers as strings or strings as numbers so we have 1 1 onto functions to convert one to another Very often we want to think of pairs or sequences of numbers as single numbers So we need a function to convert a pair to a single number and functions to take a number and nd the left or right element of the pair it represents PNXNN onto 11 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 Some years ago a CMPSCI 601 student wrote a Java ap plet that calculates these functions You are welcome to play with the applet at immermancs60lchandlerhtml 12 CMPSCI 601 Numbering Turing Machines Lecture 9 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 1 11 gt 41J gt 01 01 LJ 2LJlt 0LJ 10lt 11lt 1gt 1Igt gt 0Igt 0Igt 01gt ASCII 10 gt11 gt2LJlt 1Igt gt 0Igt 01 21 N 11 There is a simple countable listing of all TM s M0 M1 M2 l3 CMPSCI 601 The Universal Turing Machine Lecture 9 Theorem 95 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 17 at each simulated step Of course we may use multiple tapes to do this A Brookshear s 197 9 textbook has a complete diagram for a universal Turing machine on two pages Lewis and Pa padimitriou s 1981 book has a pretty complete descrip tion of one Let s now look at LU the set of numbers Pn m such that the Turing machine Mn eventually halts on input 77 We ll call this language HALT The existence of U proves that HALT is re and now we will prove that it s not recursive l4 HALT 2 Pnm TM eventually halts Theorem 96 Unsolvability of the Halting Problem HALT is 1 16 but not recursive Proof First proof based on busybeaver result HALT 2 w U eventually halts w 1 U w1 U 2 U erase tape print 1 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 t total recursive so we have a contradiction A 15 Listing All re Sets Lecture9 CMPSCI 601 can be arranged The set of all re sets W0 W1 W2 in an in nite twodimensional array mmmmmmmmmWs K 801100100 01 70101000E0 01 6011000l00 10 501010E000 01 40110E1000 01 3010l00100 10 201l001000 10 10l0101011 10 0M11010110 01 n012345678 16 CMPSCI 601 Diagonalization and Halting Lecture 9 K 2 n Mnn21 n1UPnan1 2 n nEWn Theorem 97 F13 7101716 Proof F 2 n n g2 Wm Suppose F were re Then for some 0 F 2 WC 2 nMCn21 CEK lt2 Mcc21 lt2 CEWC lt2 c6 Corollary 98 K E re Recursive 17 Theorem 99 HALT is still not recursive Proof Second proof based on diagonalization If HALT were we recursive we could use a decider for HALT to build a decider for K 2 n n E How But that would make K recursive and thus would make F re contradicting the theorem above So the HALT decider cannot exist A 18