Proving ALLTM complement not recognizable

ignougroup
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