CS 332: Theory of Computation Prof. Boston University November 2, 2021
Homework 7 – Due Tuesday, November 2, 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. You may describe Turing machines at a high-level on this assignment.
Copyright By PowCoder代写 加微信 powcoder
Problems There are 4 required problems and 1 bonus problem.
1. (Uncountable sets)
(a) Aliens from the planet Fubar’d have (countably) infinite single-strand DNA sequences from the set of nucleobases {A, C, G, T }. Let D be the set of all possible DNA sequences for residents of Fubar’d, so D = {a1a2a3 ··· | ai ∈ {A,C,G,T},i ∈ N}. Show that D is uncountable.
(b) Afunctionf :N→Nisincreasing iff(i)