DOC PREVIEW
UVA CS 302 - Problem Set 5 - Undecidability

This preview shows page 1 out of 3 pages.

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

Unformatted text preview:

UVa - cs302: Theory of Computation Spring 2008Problem Set 5 - UndecidabilityDue: Tuesday, 1 April (2:02pm)This problem set focuses on material from Classes 14-18 (through 28 March) andSipser’s book Chapter 4 and Chapter 5 (through Section 5.1). Answer all 6 ques-tions. For full credit, answers must be concise, clear, and convincing, not just cor-rect. Please staple your answer sheets before class.Honor Policy (changed from PS4). As with previous problem sets, you may dis-cuss and work on the problems with anyone you want. After your discussions,you must destroy any notes from the meetings and write up your own solutionsbased on your own understanding. Unlike in previous problem sets, this policyalso applies to notes from problem-solving sessions that pertain to questions onthe problem sets. You may preserve notes from these meetings that pertain to otherproblems or general questions, but should not use notes from these meetings thatinclude answers to specific questions from the problem set.Problem 1: Random Access Memory. Random access memory (misnamed, sinceit is not at all random) allows a program to directly reference specified memorylocations. Assume each memory location can store a single byte (8 bits) value.Show that a Turing Machine can simulate random access memory. Your machineshould be able to simulate these two instructions:1. store < location > — write the value represented by the currentsquare on the tape into location < location >. The < location > isany 32-bit integer, and < value > is any 8-bit value (represented bya single square on the tape).2. load < location > — read the value in the location < location > andwrite it onto the current square on the tape. At the end of a loadinstruction, the square under the tape head should contain the readvalue. The read value should be the last value that was stored in< location > (using a store instruction), or 0 if no value has beenstored in < location >.a. Provide an implementation-level description of a Turing Machine that cansimulate the load and store instructions. Your description should explainhow you represent memory on the tape and provide implementation-leveldescriptions of how you simulate the two instructions.PS5-1b. Is the programming language consisting of just the load and store instruc-tions above a universal programming language? (That is, is it possible to expressall possible algorithms using this language.) If it is, prove it (by explaininghow you could implement a universal Turing Machine using the load/storelanguage. If it is not, explain convincingly why not, and describe the sim-plest modifications needed to make the language a universal programminglanguage.Problem 2: Language Sizes. Consider the language,BIGGERDF A= {hA, Bi | A and B are DFAs and |L(A)| > |L(B)|}The notation |L(M )| means the size of the language described by the machine M.The size of a language is the number of strings in the language. For purposes ofthis question, you should assume the definitions about set sizes from Definition4.12.Is BIGGERDF Adecidable? Either prove that it is decidable (for example, by pro-viding a high-level description of a Turing Machine that can decide it), or provethat it is undecidable (for example, but showing that a known undecidable prob-lem can be reduced to it).Problem 3: Closure Properties. For each part, provide a clear yes or no answer,and support your answer with a brief and convincing proof.a. If A is a Turing-recognizable language, is the complement of A a Turing-recognizable language?b. If A is a Turing-decidable language, is the complement of A a Turing-decidablelanguage?c. If A and B are Turing-recognizable languages, is A ∩B a Turing-recognizablelanguage?d. If A and B are Turing-decidable language, is A ∩ B a Turing-decidable lan-guage?Problem 4: Undecidab ility. Prove that each of the following languages is unde-cidable. (Hint: show that you can reduce a known undecidable problem to theproblem of deciding the given language.)a. LIN F= {< M > |M describes a TM that accepts infinitely many strings}b. LHelloW orld= {J|J is a Java program that prints out “Hello World”}PS5-2Problem 5: Unmodifiable-Input Turing Machine. (Based on a question by RonRivest.) Consider a one-tape Turing Machine that is identical to a regular Tur-ing machine except the input may not be overwritten. That is, the symbol in anysquare that is non-blank in the initial configuration must never change. Otherwise,the machine may read and write to the rest of the tape with no constraints (beyondthose that apply to a regular Turing Machine).HALTU T M= {< M, w > |M is an unmodifiable-input TM and M halts on input w}a. What is the set of languages that can be recognized by an unmodifiable-inputTM? (Support your answer with a convincing argument.)b. Is HALTU T Mdecidable (by a regular TM)? (Support your answer with a con-vincing proof.)Problem 6: Minds and Machines. Many people find the suggestion that a humanmind is no more powerful than a Turing Machine to be disturbing, but there ap-pear to be strong arguments supporting this position. For example, consider thisargument:The brain is a collection of 100 billion neurons. Each neuron is a cell thathas inputs (known as dendrites) and outputs (synapses that emit neuro-trasmitter chemicals). The output depends on the inputs in a determin-istic way that could be simulated by a Turing Machine. The connectionsbetween neurons could also be simulated by a Turing Machine. Sinceall components of the brain could be simulated by a Turing Machine,the brain itself could be simulated by a Turing Machine. Hence, a hu-man mind is no more powerful than a Turing Machine.Write a short essay that counters this argument (although many books have beenwritten on this question, you should limit your response to no more than onepage). If you reject the premise of this question either because you do not findit disturbing to think of your mind as a Turing Machine, or you feel that the onlyway to counter this argument is to resort to supernatural (e.g., religious) notions,you may replace this question with Sipser’s Problem


View Full Document
Download Problem Set 5 - Undecidability
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 Problem Set 5 - Undecidability 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 Problem Set 5 - Undecidability 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?