Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS3800 Fall 2022 HW 6

Be sure to note the location of each problem in Gradescope

Problem 1

For each of the following sets, give the smallest complexity class in which it is contained.  Classes are listed from smallest to largest. Write your choice A through D under each numbered language and give a short justification. Your choices are:

A.  DECIDABLE

B. UNDECIDABLE but RECOGNIZABLE

C. UNDECIDABLE and UNRECOGNIZABLE but its compliment is RECOGNIZABLE

D. UNDECIDABLE and both it and its compliment are UNRECOGINZABLE

I:  {(M, x, y) l M accepts x and rejects y}

II:  {(M1, M2 ) l M2  rejects every input that M1  accepts}

III:  {(M1, M2 ) l 3 x, y such that M1  accepts x and rejects y, but M2  rejects x and accepts y} IV:  {(M)l M only rejects strings beginning with 0}

V:  {(M, w) l M accepts w using only lwl2  tape cells}

VI:  {(x) l x = 0(M) , (M) e K or x = 1(M) , (M)  K}

(Here 0(M) denotes the concatination of 0 and the encoding of M . Recall also K = {(M)l M accepts (M)} .)

Problem 2

Formally prove that L 丈m L for any undecidable L. (L is also denoted Lc .)

Problem 3

Show that for any two languages A and B there is a language J where A <T  J and B <T  J.

Problem 4

Let L = {(M) l L(M) = { ‘X’ } }. Prove that

L <T HALT.