Class Note for CMPSCI 601 at UMass(11)
Class Note for CMPSCI 601 at UMass(11)
Popular in Course
Popular in Department
This 17 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(11)
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 Turing Machines Lecture 7 M QE6s Q nite set of states 8 E Q E nite set of symbols D U E E 6 Q X E gt QUh XX X e gt s EIIOIUUn TM s are exactly like DFA s except 0 They may move either way on their tape 0 They may change tape contents 0 They have unlimited extra memory on the right end of the tape Giving a DFA some but not all of these capabilities gives some intermediate models of computation 0 The twoway DFA can still only decide regular lan guages though perhaps with many fewer states than the corresponding ordinary DFA Proving this is a good exercise in the use of the MyhillNerode The orem The linearbounded automaton can change its tape but must stay Within the bounds of the original input It recognizes the class we ll later call DSPACEn and has a corresponding grammar de nition CMPSCI 601 Example TM Lecture 7 mVRttm S q go 11 O 80 gt q0U gt 1 81 gt q1U gt H 114 80lt 81lt D sD gt hD comment nd U memorize change change amperase UtoO Utol 8 El 101d M 8 D i101 u u 8 D 1 i 01 u u 8 D 1 1 Q 1 u u 8 D110 i u u S D1101 u u q D110 l u u ql D110 14 u u 8 D110 14 1 1J mVRttm S q go 11 O 80 gt qoU gt 1 81 gt q1U gt H 114 80lt 81lt D sD gt hD S E 01 U 14 Q1 D110 U U U s D110 141m q gt1 1 U 1 1J qo Dl 1U U 1U 8 D11 U 0114 q E J 10114 h E U 101 CMPSCI 601 TM History Lecture 7 Ancient Greece Axiomatization of Geometry Early 19th Century NonEuclidean Geometry Inde pendence of Parallel Postulate Gauss Bolyai Lobachevsky Later 19th Century Rigorous Foundation of Calcu lus Real Analysis 1901 Hilbert proposes complete axiomatization of all mathematics which would reduce all proof to mechani cal procedure 1930 s Active interest in the question of what exactly a mechanical procedure might be Formal Models for Mechanical Procedures Church Lambda calculus Godel Recursive function Kleene Formal system Markov Markov algorithm Post Post machine Turing Turing machine Theorem If A and B are any two of the systems above and f is a function say from bit strings to bits then f is formalizable in A iff f is formalizable in B ChurchTuring Thesis The intuitive idea of effectively computable is captured by the precise mathematical def inition of computable in any of the above models CMPSCI 601 TM Philosophy Lecture 7 Why is a Turing machine as powerful as any other com putational model Intuitive answer Imagine any computational device It has 0 Finitely many states 0 Ability to scan limited amount per step one page at a time 0 Ability to print limited amount per step one page at a time 0 Next state determined by current state and page cur rently being read but what about randomization Note Without the potentially in nite supply of tape cells paper extra disks extra tapes etc we have just a poten tially huge nite state machine The PC on your desk with 20 GB of hard disk is a nite state machine with over 2160700070007000 states This is better modeled as a TM with a bounded number of states and an in nite tape actually meaning a nite memory that expands whenever necessary 7 CMPSCI 601 TM Functions Lecture 7 We have so far de ned the behavior of a Turing machine what it will do on a particular input Now we must de ne its semantics the way we assign meaning to its behavior A Turing machine once started may or may not eventu ally halt It could fail to halt in a number of ways run off the left end of the tape enter a loop of repeated iden tical con gurations or keep expanding the area of tape it uses forever If it does halt we want to de ne what its completed computation means One semantics dating back to Turing s original work is to say that the Turing machine accepts its input if it halts and rejects its input if it doesn t halt The language of the machine is then de ned to be the set of strings that it accepts While simple and useful for some purposes this seman tics doesn t allow us to distinguish among alwayshalting computations which after all are our main area of inter est We will design our Turing machines to have understand able behavior In particular We will design them to com pute functions from strings to strings in a particular for mat y if M on input Mud eventually E halts with output Dle otherwise 20 E E gt U Usually 20 0 1 De nition 71 Let f 2 5 gt 2 5 be a total or partial function We say that f is recursive iff El TM M f M ie W E 26 fw MW 4 Remark 72 There is an easy to compute 1 and onto map between 0 1 and N Thus we can think of the contents of a TM tape as a natural number and talk about f N gt N being recursive We may visit this issue in H W3 A partial function f N gt N is a total function f D gt N where D Q N A partial function that is not total is called strictly partial If n E N D f 2 10 CMPSCI601 Recursive re sets Lecture7 De nition 73 Let S Q 2 5 or S Q N S is a recursive set iff the function X3 is a total recursive function 1 iffEES W 0 otherwise 5 is a recursively enumerable set S is re iff the func tion p3 is a partial recursive function lif S ES p3 otherwise 11 There is also a common alternate terminology for these two concepts 0 Recursive sets are called Turing decidable because an alwayshalting TM can be designed to output 1 for inputs in the set and 0 for inputs not in it 0 Recursively enumerable sets are called Turing ac ceptable because of the semantics mentioned above a TM can be designed to halt on inputs in the set and not halt on inputs not in it 0 The word enumerable is from another semantics a set is re iff a TM can be designed that will list all the elements of the set running forever if the set is in nite 12 Proposition 74 If S is recursive then S is 716 Proof Suppose S is recursive and let M be the TM com puting X3 Build M simulating M but diverging if M 0 Thus M computes p3 Q We will see that the converse of this proposition is false as there are sets that are re Without being recursive 13 CMPSCI 601 Some Recursive Functions Lecture 7 Proposition 75 T he following functions are recursive They are all total except for peven n1 ngtltm nm nm 1 ifn is even Xevenm 0 otherwise 1 ifn is even n otherwise Proof Exercise please convince yourself that you can build TMs to compute all of these functions Q 14 CMPSCI601 Recursive 2 re 0 core Lecture7 If C is any class of sets de ne coC to be the class of sets Whose complements are in C coC 51366 Theorem 76 S is recursive l39 S and g are both 1 16 Thus Recursive re core Proof Q direction If S E Recursive then X3 is a recursive function by the de nition Therefore X3lt Egt l X3a is also a recursive function Thus 5 and g are both recursive and thus both are re 15 other direction Suppose S E re core By the de nition two machines M and M exist such that for all inputs as 19393 and M a We de ne a new machine T that runs M and M in par allel On input as T does f0rn1tooo run for n steps run M as for n steps 1 2 3 if 1 in n steps then return1 4 5 if M 1 in n steps then return0 Thus T X3 X3 is a recursive function and thus 5 E Recursive Q 16 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 17
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'