# 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
(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.” 