Given are the following languages:
$L_1 = \{0\}\\ L_2 = \{w \in \{0,1\}^{*} | L(M_w) = \{0\}\}\\ L_3 = \{w \in \{0,1\}^{*} | M_w \text{ stops at all entries }\} \\ L_4 = \{w \in \{0,1\}^{*} | L((0|1)^{*}0) \cap\ L(M_w) = \emptyset \} $
(Whereas $M_w$ describes the turing machine with coding $w$.)
Now I want to decide whether these languages are decidable, undecidable or semi-decidable. My intuitions are the following:
- is decidable, since its a finite set.
- is undecidable. Proof: Rice's theorem with f as the zero map.
- is undecidable. Proof: Reduction from the halting problem on the empty tape.
- probably also undecidable, but I have not idea how to proof it.
Can you tell me whether these assumptions are right and how I could proof number 4? Thank you!