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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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$ Commented Apr 19, 2013 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$ Commented Apr 19, 2013 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$ Commented Apr 19, 2013 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$ Commented Apr 19, 2013 at 18:49

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.