DOC PREVIEW
Berkeley COMPSCI 172 - Undecidable/non-Turing Recognizable Languages

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS 172: Computability and Complexity, Spring 2010 S. A. Seshia & O. EtesamiHW 7: Undecidable/non-Turing Recognizable LanguagesAssigned: March 28, 2010 Due: April 5, 2010Note: Take time to write clear and concise solutions. Confused and long-winded answers may bepenalized. Consult the course webpage for course policies on collaboration.1. (8 points) Read about Rice’s Theorem in Problem 5.28 in Sipser’s book. A form of Rice’sTheorem is stated as follows:Let P be a language of Turing machine descriptions (i.e., containing strings of the form hM iwhere M is a TM), where P satisfies two conditions:1) P is non-trivial: There exist TMs M1and M2such that hM1i ∈ P but hM2i 6∈ P .2) P is a property of (only) a TMs language: For any TMs M1and M2such that L(M1) =L(M2), hM1i ∈ P if and only if hM2i ∈ P .Then P is undecidable.The proof of Rice’s Theorem (Prob. 5.28) is given at the back of Chapter 5 of Sipser’s book.Review it, and then answer the following questions:(a) Show that both of the above conditions of Rice’s theorem are necessary. In other words,show, for each condition, that leaving it out makes P decidable for some P .(b) Using Rice’s Theorem, prove that the following language is undecidable:ALLTM= {hMi | M is a TM and L(M) = Σ∗}2. (5 points) Prove that there exists a subset of {1}∗which is not Turing-recognizable.3. (9 points)(a) (5 points) Let L1= {hM, wi | Turing machine M on input w attempts to move its headleft at some point during its computation when its head is on the left-most tape cell}.Prove that L1is undecidable.(b) (4 points) Let L2= {hM, wi | Turing machine M on input w attempts to move its headleft at some point during its computation}. Prove that L2is decidable.4. (8 points) [G¨odel’s Incompleteness Theorem]One of the most important results of 20th century logic (and arguably of all 20th century1mathematics) was the discovery that there are some true mathematical statements that can-not be proven using the standard axioms of mathematics. This 1931 result by Kurt G¨odel isknown as G¨odel’s Incompleteness Theorem. In this problem, you will prove one version ofG¨odel’s Theorem using what we know about Turing machines, 79 years too late to revolu-tionize modern mathematics.(The actual proof given by G¨odel is a little more complicated, since Turing Machines hadn’tbeen invented yet, but it relies on the same basic notion of diagonalization, and the two resultsare intimately related.)Some preliminaries: we say that a system of mathematics is consistent if there exists a specialproof-checking Turing machine M∗that can verify or reject any proof that it is given in thelanguage of that system. In other words, there exists a machine M∗that decides the languageP ROOF S = {hP, T i| P is a valid proof of statement T}Assume that our system of mathematics is consistent, so that we can check algorithmicallywhether a proof is correct. Assume for simplicity’s sake that any statement T in our system ofmathematics is either true or false - exactly one of T or not(T ) is true. For this question, youcan express a mathematical statement in the usual way using English, rather than encoding itinto any special logical language.(a) Suppose for a contradiction that every true statement Tihas a proof Pi. Using thisassumption, give a Turing machine that is a decider for the language T ST M T S ={hT i| T is a true statement }.(b) Use the result of part (a) to construct a Turing machine that solves the halting problem.(c) Conclude that there exists a true theorem that does not have a proof, proving


View Full Document

Berkeley COMPSCI 172 - Undecidable/non-Turing Recognizable Languages

Download Undecidable/non-Turing Recognizable Languages
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Undecidable/non-Turing Recognizable Languages and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Undecidable/non-Turing Recognizable Languages 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?