CS 332: Theory of Computation Prof. Boston University October 21, 2021
Homework 6 – Due Tuesday, October 26, 2021 at 11:59 PM
Reminder Collaboration is permitted, but you must write the solutions by yourself without as- sistance, and be ready to explain them orally to the course staff if asked. You must also identify your collaborators and write “Collaborators: none” if you worked by yourself. Getting solutions from outside sources such as the Web or students not enrolled in the class is strictly forbidden.
Note You may use various generalizations of the Turing machine model we have seen in class, such as TMs with two-way infinite tapes, stay-put, or multiple tapes. If you choose to use such a generalization, state clearly and precisely what model you are using.
Copyright By PowCoder代写 加微信 powcoder
Problems There are 5 required problems.
1. (ALLREX) Consider the following computational problem: Given a regular expression R (over some
alphabet Σ), is the language generated by R equal to Σ∗?
(a) Formulate this problem as a language ALLREX, in the style of the languages described in
Sisper Chapter 4.1.
(b) Show that ALLREX is decidable. You may give a high-level description of the Turing machine your construct.
Hint: Following the examples in Sipser Chapter 4.1, you may assume that the procedures we’ve seen in class for converting back and forth between automata and regular expressions can be implemented on Turing machines, and just cite these constructions.
2. (Universal TM) In this short programming exercise, you will (sort of) build the universal Turing machine. Hopefully this makes the idea of designing a Turing machine that takes another Turing ma- chine as input less disturbing. Recall the language ATM = {⟨M, w⟩ | M is a TM accepting input w}. Determining membership in this language corresponds to the computational problem of determining whether TM M accepts input w.
The file universal tm.py contains starter code that will help you implement a Turing machine Python program recognizing this language. Implement a program that prompts the user for an (appropriately encoded) TM-with-stay-put M and a binary string w, outputting i) the sequence of configurations M enters when run on w, and ii) whether M accepts or rejects input w, if it terminates. Your program is (necessarily) allowed to run forever if M runs forever on w. The starter code file describes the expected syntax for the input and output of your solution.
This is not a software engineering class, so your program is allowed to fail arbitrarily (including failing silently) if its inputs do not correctly encode a TM and a binary string.
If you really don’t like Python, you can implement your program in another high-level programming language (Java, C++, Haskell, …) that the grading staff can read. (No Malbolge, please.) The downside is that you won’t have the starter code to parse the input for you.
3. (Code as data) Consider the following description of a three-tape TM H. Algorithm: H(⟨M,N⟩)
Input : Binary encoding of two basic TMs M and N, i.e., ⟨M,N⟩ ∈ {0,1}∗
1. 2. 3. 4. 5. 6.
Copy the string ⟨M⟩ to tape 2.
Copy the string ⟨N⟩ to tape 3.
Repeat the following three steps forever:
Simulate N for one step on tape 2.
Simulate M for one step on tape 3.
If either machine accepts, accept. If both machines have rejected, reject. Else, continue.
Also, define the following three TMs, whose descriptions will be supplied as input to H. Algorithm: M1(x)
Algorithm: M2(x)
Algorithm: M3(x)
Input : String x ∈ {0, 1}∗
1. Ignore the input x and reject.
Input : String x ∈ {0, 1}∗
1. If x = ⟨M1⟩, accept. Otherwise, reject.
Input : String x ∈ {0, 1}∗
1. LetM betheTMsuchthat⟨M⟩=x.
2. For i = 1,2,3,…:
3. For each string y where |y| ≤ i:
4. Run M on input y for i steps. If it accepts, accept.
(a) What is L(M1)? (b) What is L(M2)? (c) What is L(M3)?
(d) Is ⟨M1, M2⟩ ∈ L(H)? Explain why or why not.
(e) Is ⟨M1, M3⟩ ∈ L(H)? Explain why or why not.
(f) What is the language L(H) recognized by H?
(g) Is H a decider for the language L(H)? Explain why or why not.
4. (EVENTM) Consider the following computational problem: Given a Turing machine M (over some alphabet Σ), does there exist a string w of even length such that M accepts input w?
(a) Formulate this problem as a language EVENTM.
(b) Show that EVENTM is Turing-recognizable. You may give a high-level description of the Turing machine your construct.
Hint: Think about the TM M3 from Problem 3 above. Why was it constructed that way? A similar idea will be helpful for this problem.
5. (Countable sets)
(a) Aliens from the planet Foobar have finite single-strand DNA sequences consisting of the nucle- obases A, C, G, and T. For example, ACGTTAG and CGATCGACTGCA are both possible DNA sequences. Let F be the set of all possible DNA sequences for residents of Foobar. Show that F is countable.
(b) Aliens from the planet Foobarbaz have finite single-strand DNA sequences from a countably infinite set of nucleobases {A1, A2, A3, . . . }. For example, A2A4A8A1A9 and A3A747A9999999A4 are both possible DNA sequences. Let B be the set of all possible DNA sequences for residents of Foobarbaz. Show that B is countable.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com