这个作业是完成计算机原理相关的理论问题

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