Proving ALLTM complement not recognizable

Problem Detail: 

A few definitions..

$$ \begin{align*} \mathrm{ALL}_{\mathrm{TM}} &= \Bigl\{\langle M \rangle \,\Big|\, \text{$M$ a Turing Machine over $\{0,1\}^{*}$},\;\; L(M) = \{0,1\}^{*} \Bigr\} \\[2ex] \overline{\mathrm{ALL}}_{\mathrm{TM}} &= \Bigl\{\langle M \rangle \,\Big|\, \text{$M$ a Turing Machine over $\{0,1\}^{*}$},\;\; L(M) \ne \{0,1\}^{*} \Bigr\} \\[2ex] B_{\mathrm{TM}} &= \Bigl\{\langle M \rangle \,\Big|\, \text{$M$ is a Turing Machine over $\{0,1\}^{*}$},\;\; \varepsilon \in L(M) \Bigr\} \end{align*} $$

We are showing a reduction from $B_{\mathrm{TM}}$ to $\overline{\mathrm{ALL}}_{\mathrm{TM}}$. In my notes I have the following solution to this problem which I'm trying to understand.

1. Let $\alpha \in \{0,1\}^*$. Check that $\alpha$ is of form $\langle M \rangle$, where $M$ is a TM over $\{0,1\}$. Else, let $f(\alpha)$ be anything not in $\overline{\mathrm{ALL}}_{\mathrm{TM}}$.

2. Let $f(\alpha)$ be $\langle M' \rangle$, where $M'$ on $x$ runs $M$ on $\varepsilon$ (blank string) for up to $|x|$ steps. If $M$ accepts (in that time), then $M'$ rejects. Otherwise, $M'$ accepts.

What I'm trying to understand is why must we run the TM $M'$ for $|x|$ steps for this to work? If we change the part #2 of the transformation to the following, why wouldn't this work?

• Let $f(\alpha)$ be $\langle M' \rangle$, where $M'$ on $x$ runs $M$ on $\varepsilon$ (blank string). If $M$ accepts, reject. Otherwise accept.

Which then it follows that $\varepsilon \in L(M) \!\iff\! L(M) = \varnothing$, that is $L(M) \neq \{0,1\}^*$.

Asked By : Steven

Answered By : Shaull

First, there is a small typo in (1) - if $\alpha$ is not a legal encoding, then you should return something that is in $ALL_{TM}$ (since you are reducing to the complement).

For your question: the key point here is that a TM does not always halt on its input. Thus, the phrase "otherwise accept" in your suggestion for (2) is not computable. If you run $M$ on $\epsilon$, and $M$ does not halt, then the lanugage of $M'$ will be $\emptyset$, which makes the reduction fail.

In general, when you perform reductions that output a machine that simulates another machine, you must always consider the possibility that the latter will not halt. If this poses a problem (as it does here), a good trick to circumvent it is to limit the step number, and since often you want this limit to exist, but to be ``unbounded'', then using the input for the machine as a limit is a good idea.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11411