Question $1$:

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$)$ is a TM and $1011$inL$(M).$

$($b$)|)$:$\}$ is a TM and $\{$:$L(M)={}^{**}\}.$

$($c$)$ is a TM and $.$

Question $2$:

A tough word. Let $=\{0,1\}.$ Given a fixed word $w_{0}in{}^{**},$ is the language $|)$:$\}$ is a TM with input alphabet $$ that accepts $\{$:$w_0\}$

decidable or not? Or does it depend on $w_0?$

Question $3$:

Halt when started on blank tape. Consider the language

$HAL{T}_{}=\{($:$M$:$)|M$ halts $on$ input $\}$

Can Rice's theorem be used to directly show that $HAL{T}_{}$ 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.

Question $4$:

Explicit mapping reduction. Let $=\{0,1\}$ and consider the following

languages $A,$Bsube${}^{**}$ :

$A=\{win{}^{**}||w|<mn>4</mn><mi>\}</mi>$

$B=\{win{}^{**}||w|7\}$

Show that $A{?}_{m}B$ by defining an explicit reduction $f$ from $A$ to $B.$