# BEST代写-线上编程学术专家

Best代写-最专业靠谱代写IT | CS | 留学生作业 | 编程代写Java | Python |C/C++ | PHP | Matlab | Assignment Project Homework代写

# 计算机原理代写 | 4-hw: Computational Problems, Undecidability, and Mapping Reduction CSE105SP20

### 计算机原理代写 | 4-hw: Computational Problems, Undecidability, and Mapping Reduction CSE105SP20

4-hw: Computational Problems, Undecidability, and Mapping
Reduction
CSE105SP20
Due: Sunday May 31 at 11:00PM (on Gradescope)
The same homework policies apply as in 1-hw. Please see that assignment writeup for details about
• Collaboration policy and group size.
• Submission instructions.
• Typed work.
• Expectations for justification
Reading and extra practice problems: Sipser Chapter 4, Section 5.3. Chapter 4 exercises 4.1,
4.3, 4.4., 4.5. Chapter 4 Problems 4.29, 4.30, 4.32. Chapter 5 exercises 5.4, 5.5, 5.6, 5.7. Chapter 5
problems 5.10, 5.11, 5.16, 5.18.
Key Concepts: computational problems, diagonalization, undecidability, unrecognizability, computable function, mapping reduction.
1. Consider the following sets representing computational problems
Q1 = {hMi | M is a DFA over {0, 1} and |L(M)| = 1}
Q2 = {hMi | M is a DFA over {0, 1} and L(M) is finite}
Q3 = {hMi | M is a DFA over {0, 1} and 101 ∈ L(M)}
(a) (8 points) Find an element of Q1. Include in your answer both a precise description of this
element and justification that this element satisfies the condition for membership in Q1.
(b) (24 points) Find examples (also known as witnesses) that prove each of the following:
i. Q2 6⊆ Q3, i.e. formally ∃x( x ∈ Q2 ∧ x /∈ Q3 ).
ii. Q3 6⊆ Q2, i.e. formally ∃x( x ∈ Q3 ∧ x /∈ Q2 ).
iii. Q2 ∩ Q3 6= ∅, i.e. formally ∃x( x ∈ Q2 ∧ x ∈ Q3 ).
For each example you must include
• A precise description of the example element.
• Justification that this element is a valid example, making specific references to the
definitions of the sets and set operations involved and connecting them to the element
you choose.
1
(c) (18 points) (Graded for fair effort completeness)
i. Prove that Q1 is decidable.
ii. Prove that Q2 is decidable.
iii. Prove that Q3 is decidable.
2. Mapping reductions can be used in multiple ways to calibrate the computational difficulty of a
computational problem. In this question, you’ll consider examples of these applications.
(a) (10 points) (Graded for fair effort completeness) Give an example where mapping reduction
is used to prove that a problem is decidable. To do this, identify two problems P1 and P2,
prove that P1 ≤m P2, prove that P2 is decidable, and therefore conclude that P1 is also
decidable.
For each part, you can either cite results proved in the textbook / class slides or provide an
original proof. Clearly label your work as original or with the source.
(b) (10 points) (Graded for fair effort completeness) Give an example where mapping reduction
is used to prove that a problem is undecidable. To do this, identify two problems P3 and
P4, prove that P3 ≤m P4, prove that P3 is undecidable, and therefore conclude that P4 is
also undecidable.
For each part, you can either cite results proved in the textbook / class slides or provide an
original proof. Clearly label your work as original or with the source.
3. Fix Σ = {0, 1} for this question. For each part below, you must choose sets from the following
list:
∅, ATM, ATM , HALTTM, HALTTM, ETM, ETM, EQTM, EQTM
You may use each set from the list at most once in the examples below.
(a) (10 points) Find sets X, Y from the above list for which the computable function
F = “On input x
1. Output h i.”
witnesses the mapping reduction X ≤m Y . Clearly identify your choice of X and Y . Justify
your answer by proving that, for all strings x, x ∈ X iff F(x) ∈ Y .
(b) (10 points) Find sets A, B for which the computable function
H = “On input x
1. Check if x = hM, wi for M a Turing machine and w a string. If so, go to step 3.
2. If not, output h i.
3. Construct the Turing machine M0
x = “On input y,
1. If y 6= w, reject.
2. Otherwise, run M on w.
3. If M accepts, accept. If M rejects, accept.”
4. Output hM0
x
i.”
2
witnesses a mapping reduction A ≤m B. Clearly identify your choice of A and B. Justify
your answer by proving that, for all strings x, x ∈ A iff H(x) ∈ B.
(c) (10 points) (Graded for fair effort completeness) For either F(x) from part (a) or H(x) from
part (b) find two more mapping reductions that are witnessed by this function. You may
use sets that are not in the list at the start of this question for your example. Justify the
mapping reductions you include.
3 