Question

L = {<M,s> : M rejects ss, but accepts exactly two other strings ending in s} . Prove that L ∉ D using a reduction from H; do not use Rice's theorem.

Answer 1

To prove that the given language is undecidable, do the following: reduce from the language $H = \{\langle M, w\rangle \mid M \text{ halts on } w\}$ .

Let $\langle M, w\rangle$ be an instance for $H$. Output the following: $\langle M', 1\rangle$ where M' does the following: On input x, if x doesn't end in 1, it rejects. If $x = 11$, it rejects. Otherwise, it runs M on w, and if M halts on w, accepts x.

To prove that this is a valid reduction, argue as following. If M halts on w, then M' accepts all strings ending with 1 except for 11, hence $\langle M', 1\rangle \in L$ . Otherwise M' accepts nothing, hence $\langle M', 1\rangle \not\in L$ . This proves that this is a reduction from H to L.

Thus, given that H is undecidable, L is undecidable as well.

Comment in case of any doubts.