Prove that $\overline{L}$ is not recognizable by showing that $B_{TM} \le_m L$

312 Views Asked by At

$\textbf{Problem}:$

$L$ = $\{\langle M \rangle$ | $M$ is a Turing machine over $\{0, 1\}$ such that for some $x \in \{0,1\}^*$, $M$ does not halt on input $x\}$.

$B_{TM}$ = $\{ \langle M \rangle$ | $M$ is a Turing machine over $\{0, 1\}$ and $M$ accepts $\epsilon\}$.

$\textbf{Attempted solution}:$

To show that $L$ is not recognizable we must show that $B_{TM} \le_m L$.

Lets define the computable function $f: \{0,1\}^* \rightarrow \{0,1\}^*$ where for some $w \in \{0,1\}^*$, we must show that, $w \in B_{TM} \Longleftrightarrow f(w) \in L$.

First we check that the input $w$ is of the form $\langle M \rangle$, if not reject.

Assume that the input $w$ is of the form $\langle M \rangle$ then we construct a new Turing machine $M'$ such that $M'$ ignores its inputs and halts only when $M$ does not accept. $M'$ then runs $M$ on the blank tape.

If $\epsilon \in \mathcal{L}(M)$ then $M'$ never halts since $M$ always accepts so $\langle M' \rangle \in L$.

If $\epsilon \notin \mathcal{L}(M)$ then $M'$ halts on all strings and therefore $\langle M' \rangle \notin L$.

Therefore we can conclude $w \in B_{TM} \Longleftrightarrow f(w) \in L$ where $f(w) = \langle M' \rangle$.


The part that I am not certain about is the method by which $M'$ is constructed. Is it correct to say $M'$ halts only when $M$ does not accept? If not, what is the trick to demonstrate that $B_{TM} \le_m L$?

Thanks.