Computability and Languages
Computability and Languages CSE 460
Popular in Course
Popular in Computer Science and Engineering
This 4 page Class Notes was uploaded by Donnell Kertzmann on Saturday September 19, 2015. The Class Notes belongs to CSE 460 at Michigan State University taught by Staff in Fall. Since its upload, it has received 10 views. For similar materials see /class/207426/cse-460-michigan-state-university in Computer Science and Engineering at Michigan State University.
Reviews for Computability and Languages
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: 09/19/15
CSE 460 Review Worksheet 11 Answers Part 1 Why study the REC language classes These questions are designed to make you review why we study the REC and RE language classes 1 Why do we study the REC language class One of our purposes in this course is to study what are the fundamental capabilities and limitations of computers If we consider computers to be problem solving devices then this boils down to studying what problems can and cannot be solved by computers The REC language class represents the problems that can be solved and thus represents the limits of what computers can solve and that is why we study it 2 Why is it interesting to show a language L is in the REC language class This implies L and its corresponding problem are solvable and thus fall within the capabilities of what computers can do as problem solving devices 3 Why is it interesting to show a language L is not in the REC language class This implies L and its corresponding problem are unsolvable and thus beyond the limits of what computers can do as problem solving devices Part 11 Showing a language L is recursive This part reviews the ways we have for showing a language L is recursive 1 What is the de nition of a language L being recursive There exists a program P which solves L 2 Given the above de nition what is one way to prove that a language L is recursive Construct a program P which solves L 3 Suppose we know that languages L1 and L2 are recursive What are some alternative ways to prove that a third language L3 is recursive We could try and show that L3 L1 op L2 where op is some operation that the set of recursive languages is closed under Part 111 Showing a language L is not recursive This part reviews the ways we have for showing a language L is not recursive 1 De ne what it means for a language L to not be recursive That is apply a logical not operation to your de nition of a language L being recursive When we apply the not the There exists turns into a For all and we get For all programs P P does not solve L 2 How did we prove that the Halting Language Problem is not recursive We used the diagonalization technique 3 Given that the Halting Language H is not recursive give an IFTHEN statement about H and a second language L that would prove that L is not recursive If L is recursive then H is recursive or If H is not recursive then L is not recursive 4 What general technique did we use for proving the type of IFTHEN statement described in the question above Answerpreserving input transformations 5 Suppose we know that language L1 is not recursive and language L2 is recursive What are some alternative ways to prove that a third language L3 is not recursive We could try and show that L1 L3 op L2 where op is some operation that the set of recursive languages is closed under Part IV Closure Properties What and Why These questions are designed to make you review the de nitions of what closure properties are and why proving closure properties is interesting 1 What does it mean when I say a language class LC is closed under set operation 0 For any languages L in LC if I apply operation 0 to these languages I get another language in LC 2 I have said that a closure property statement really represents an in nite set of facts What do I mean when I say this I mean that it represents all statements of the form Ll op L2 is in LC where L1 and L2 are in LC and op is a binary operation Since there can be an in nite number of languages L1 and L2 in LC this is an in nite set of facts 3 Suppose O is a binary operation express the fact that language class LC is closed under set operation 0 in rstorder logic For all L1 and L2 in LC L1 0 L2 is in LC 4 Given parts II and III what are two reasons for being interested in proving closure properties for the language class REC Closure properties give us new ways to prove that a problemlanguage is recursive and they give us new ways to prove a problem language is not recursive 5 Suppose you want to write a program P1 to solve language L1 Furthermore suppose you know that L1 L2 intersect L3 and you have already written programs P2 and P3 which solve L2 and L3 respectively How would you write a program P1 I would write P1 using P2 and P3 as subroutines 6 Given your answer to question 5 what is another reason we are interested in proving closure properties In particular why are we interested in the constructions contained in these proofs These constructions provide speci c methods for constructing programs to solve problems given existing programs which solve related problems Part V Proving Closure Properties This section reviews how we prove closure properties for the REC language class 1 State in English what it means when I say the REC language class is closed under set intersection If I intersect any two recursive languages the resulting language is recursive 2 Describe what the rst line of a generic element proof that the REC language class is closed under set intersection must be The rst line should be Let L1 and L2 be arbitrary recursive solvable languages 3 Given the rst line of the proof and the de nition of recursive languages what is the second line of a proof that the REC language class is closed under the set intersection operator Let P1 and P be the corresponding programs which solve languages L1 and L2 Note these programs must exist by de nition of a language being recursive 4 Now give the last line of the proof that the REC language class is closed under the set intersection operator L1 intersect L2 is recursive solvable 5 Given the last line of the proof and the de nition of recursive languages what is the second to last line of a proof that the REC language class is closed under the set intersection operator There exists some program P3 which solves language L1 intersect L2 6 Given the second line of the proof and the second to last line of the proof we want to come up with a construction that takes what as input and produces what as output It should take two programs P1 and P2 as input and produce program P3 which decides LP1 intersect LPz as output assuming P1 and P2 decide their respective languages 61 Is this construction an algorithm Yes 7 Besides coming up with this construction what else do we need to do to nish the proof 7 l Argue that the output of the construction processes the strings in the intersection correctly The resulting program P3 must halt and say yes on all such strings 72 Argue that the output of the construction processes the strings not in the intersection correctly The resulting program P3 must halt and say no on all such strings 8 Repeat questions 17 for any other set operation 9 Repeat questions 17 for any set operation and the RE language class 91 How does your answer to question 72 differ when dealing with the RE language class instead of the REC language class Now we must allow the program to also loop and or crash It just cannot say yes Part VI Reductions This part reviews the reduction proof technique 1 What can I conclude from the following two facts 11 L1 is recursive 12 If L1 is recursive then L2 is recursive L2 is recursive 2 Describe how we use the answer to question 1 in reallife programming We often build programs to solve problems using programs which solve other problems as subroutines 3 What can I conclude from the following two facts 31 L1 is not recursive 32 If L2 is recursive then L1 is recursive L2 is not recursive 4 Describe how we use the answer to question 3 in this course We use the basic outline described in problem 3 to prove new problems are not recursive 5 Can the inputtransformation technique prove a language L2 is not recursive if there is no known not recursive language L1 No we need an existing known not recursive language 6 What language do we typically use as language L1 The Halting problem 7 Which statement 31 or 32 does an inputtransformation help prove Statement 32 8 In proving statement 32 the first line of the proof is an assumption What is that assumption Assume that L2 is recursive In general when proving an if then statement assume the if clause is true as the Ifthen statement is trivially true when the if clause is false 9 Given the definition of recursive languages what is the next line of the proof Let P2 be the program which solves L2 Again any time we have a recursive language by the definition of a language being recursive there must be some program which solves it Give that program a name
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'