Class Note for CMPSCI 601 at UMass(39)
Class Note for CMPSCI 601 at UMass(39)
Popular in Course
Popular in Department
This 12 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 14 views.
Reviews for Class Note for CMPSCI 601 at UMass(39)
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 4 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 CMPSCI 601 Example TM Lecture 4 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 4 Hilbert s Program 1901 Give a complete axiomization of all of mathematics Such a complete axiomization would have provided a mechanical procedure to churn out exactly all true state ments in mathematics This led to active interest in 1930 s in the question What is a mechanical procedure Church Lambda calculus Godel Recursive function Kleene Formal system Markov Markov algorithm Post Post machine Turing Turing machine Fact The above models are all de ne exactly the same class of computable functions ChurchTuring Thesis The intuitive idea of effectively computable is captured by the precise de nition of com putable in any of the above models 4 CMPSCI 601 TM Philosophy Lecture 4 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 21607000900900 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 5 CMPSCI 601 TM Functions Lecture 4 y if M on input Mud eventually E halts with output Dle otherwise 20 E E gt U Usually 20 0 1 De nition 41 Let f 26 gt 26 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 42 There is an easy to compute 1 and onto map between 0 l 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 W2 Partial function f N gt N is a total function f D gt N where D g N A partial function that is not total is called strictly partial If n E N D f 2 CMPSCI601 Recursive re sets Lecture4 De nition 43 Let S g 25 or S g N S is a recursive set iff the function X3 is a total recursive function 1 lf S ES W 0 otherwise 5 is a recursively enumerable set S is re iff the func tion p3 is a partial recursive function 1 lf S ES mm 2 otherwise Proposition 44 If S is recursive then S is re 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 CMPSCI 601 Some Recursive Functions Lecture 4 Proposition 45 T he following functions are recursive They are all total except for peven n1 ngtltm nm 2 nm 1 ifniseveh Xevenm 0 otherwise 1 ifn is even 01 otherwise Proof Exercise please convince yourself that you can build TMs to compute all of these functions Q CMPSCI601 Recursive 2 re 0 core Lecture4 If C is any class of sets de ne coC to be the class of sets Whose complements are in C coC 51366 Theorem 46 S is recursive l39 S and g are both 1 16 Thus Recursive re core Proof If S E Recursive then X3 is a recursive function Thus so is X a l X3a Thus 5 and g are both recursive and thus both re 10 Suppose S E re cone mMW mMW De ne T MIIM on input 1 form 2 1tooo 2 run for n steps 3 if 1 in n steps then return1 4 run M a for n steps 5 if M 1 in n steps then return0 Thus 2 X3 and thus 5 E Recursive 11 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 12
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'