4
$\begingroup$

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\}^*$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, I've fixed the error. However I'm still not understanding exactly why this works. For example, let's assume the turing machine M would accept ε in 2|x| steps. So ε $\in$ L(M), if we were to run it for long enough. However, when we're using M', it doesn't run long enough and simply "assumes" that ε isn't in the language of M. So we've got a case where ε $\in$ L(M) => L(M') = {0,1}*, and not ε $\in$ L(M) <=> L(M') $\neq$ {0,1}*. $\endgroup$ – Steven Apr 19 '13 at 17:01
  • $\begingroup$ Observe that if $M$ accepts $\epsilon$, then it accepts it in $k$ steps for some fixed k. Then, when you feed $M'$ with an input $x$ such that $|x|>k$, the simulation would succeed, and $M'$ would reject. This uses the fact that $|x|$ can be arbitrarily large, and in particular greater than $k$. $\endgroup$ – Shaull Apr 19 '13 at 17:08
  • $\begingroup$ After further reading I stumbled across this definition of mapping reducible which would have helped a lot if I had read it before: f: $\sum^* \rightarrow \sum^*$ is computable if there is a turing machine M over $\sum$ such that for all $\alpha \in \sum^*$, M on $\alpha$ eventually halts with output $f(\alpha)$ $\endgroup$ – Steven Apr 19 '13 at 18:20
  • $\begingroup$ Don't be confused: the reduction must halt. The machine it outputs need not halt! This is a very important point. $\endgroup$ – Shaull Apr 19 '13 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.