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, com- putable function, mapping reduction.
1. Consider the following sets representing computational problems
Q1 ={⟨M⟩|M isaDFAover{0,1}and|L(M)|=1} Q2 = {⟨M⟩ | M is a DFA over {0,1} and L(M) is finite} Q3 ={⟨M⟩|M isaDFAover{0,1}and101∈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 ̸⊆ Q3, i.e. formally ∃x( x ∈ Q2 ∧ x ∈/ Q3 ). ii. Q3 ̸⊆ Q2, i.e. formally ∃x( x ∈ Q3 ∧ x ∈/ Q2 ).
iii. Q2 ∩ Q3 ̸= ∅, 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
⟩.”
witnesses the mapping reduction X ≤m Y . Clearly identify your choice of X and Y . Justify
1. Output ⟨
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. Checkifx=⟨M,w⟩forM aTuringmachineandwastring. Ifso,gotostep3.
2. If not, output ⟨
3. Construct the Turing machine Mx′ = “On input y,
1. If y ̸= w, reject.
2. Otherwise, run M on w.
3. If M accepts, accept. If M rejects, accept.”
4. Output ⟨Mx′ ⟩.”
⟩.
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