Instructions: This homework is to be submitted on GradeScope as a single  pdf (not in parts) by 11:59 pm on the due date.  You may either type your solutions in a word processor and print to a pdf, or write them by hand and submit a scanned copy.  Do write and submit your answers as if they were a professional report.  There will be point deductions if the submission isn’t neat (is disordered, difficult to read, scanned upside down, etc....).

Begin by reviewing your class notes, the slides, and the textbook.  Then do the exercises below. Show your work. An unjustified answer may receive little or no credit.

Note: Problems 9-10 require Tuesday’s class.

Read: 7.1, 7.2 (for Tuesday) and 7.3, 7.4 (for Friday)

1.  [9  Points] Rice’s  Theorem. Use Rice’s theorem to prove the undecidability of the following languages.  Do explain why you may use the Theorem and how you are using it: state the property of involved machines, and explain why the two conditions are satisfied.

(a) {⟨M⟩ |  M is a TM and 1011 ∈ L(M)} .

(b) ALLTM  = {⟨M⟩ |  M is a TM and L(M) = Σ* } .

(c) ETM  = {⟨M⟩  |  M is a TM and L(M) = ∅} .

2.  [10 Points] A tough word. Let Σ = {0, 1}.  Given a fixed word w0  ∈ Σ* , is the language

{⟨M⟩ |  M is a TM with input alphabet Σ that accepts w0 }

decidable or not? Or does it depend on w0 ?

3.  [10 Points] Halt when started on blank tape. Consider the language

HALTε = {⟨M⟩ |  M halts on input ε}

Can Rice’s theorem be used to directly show that HALTε is undecidable?

(a) Suppose you try to use Rice’s Theorem. What property P(M) of Turing machines M would be relevant here?

(b) Is this property trivial?  Explain why it is, or prove that it is not.

(c) Is this a property of languages? Explain why it is, or prove that it is not.

4.  [10 Points] Explicit mapping reduction. Let Σ = {0, 1}  and consider the following languages A, B ⊆ Σ*  :

A = {w ∈ Σ*  |    |w|  < 4}

B = {w ∈ Σ*  |   |w|  ≥ 7}

5.  [6  Points] Definitions. Let  A, B ⊆ Σ*   and  assume  that  A  is  decidable.   Which  of the following statements are guaranteed to be true (whatever B is)?  For each of these statements, give either a reference, a proof, or a counterexample.

(a) A ≤T  B

(b) A ≤m  B

6.  [12 Points] Accept, Halt, Loop on input ε.  In this problem, we consider the languages

ACCEPTε = {〈M）| M accepts ε}

HALTε = {〈M）| M halts on input ε}

LOOPε = {〈M）| M loops on input ε}

It is known from class (slide 155, lecture 22b) that language ACCEPTε is undecidable.

(a) Prove that HALTε is undecidable by constructing a mapping reduction ACCEPTε 参m  HALTε .

(b) Prove that HALTε is recognizable by describing a recognizer.

(c) Prove that LOOPε is not recognizable.

7.  [10 Points] Showing that a language is enumerably complete.

Suppose that A, B ⊆ Σ*  are languages such that

(0) A ≤m  B

(1) A is enumerably complete

(2) B is enumerable

Prove that B is enumerably complete.  That is, explain why B satisfies all conditions in

the definition of enumerably complete languages.

(Compare with lecture 23b.)

8.  [11 Points] Language L such that neither L nor L is recognizable. Let Σ = {0, 1} and define the language L by

L = {w E Σ*  | either  w = 0x for some x E ATM    or  w = 1y for some y E ATM  }

(a) Prove that ATM ≤m L.

(b) Prove that ATM ≤m  L.

(c) Prove that neither L nor L is recognizable.

9.  [11 Points] Simulating a TM  with a Semi-Thue System. In this problem,  con- sider the Turing machine M with Σ = {0, 1}, Γ = {0, 1, }, Q = {s,qaccept ,qreject } and transitions

s s R

s       0       s        0       R

s       1   qaccept        1       R