0
$\begingroup$

First definition:

$A_{TM}$ = $\{ <M,w> | $M is a TM and M on w accepts$ \}$

Second definition:

$E_{TM} = \{ <M> |$ M is a TM and L(M) = $\phi \}$

Let $T^{A_{TM}}$ be an oracle Turing machine with an oracle $A_{TM}$. We want to show that $E_{TM}$ is Turing reducible to $A_{TM}$.

$T^{A_{TM}}$ = "On input $<M>$, where M is a TM:

  1. Construct a TM N:
  1. N = "On any input:
  2. For i=0, 1, 2, 3. Run M on s_i for i steps where $s_i \in \Sigma^*$ and $\Sigma^*=\{s_0, s_1, s_2, .... \}$.
  3. If M accepts any of these strings, then accept."
  1. Ask the oracle: Is $<N, 0> \in A_{TM}$.
  2. If the oracle answers NO, accept. If YES, reject."

Now, Sipser said in pp. 236-237, "If M's language isn't empty, N will accept every input and in particular, input 0. Hence the oracle will answer YES, and $T^{A_{TM}}$ will reject. Conversely, if M's language is empty, $T^{A_{TM}}$ will accept."

My question: Why N will accept every input and in particular, input 0? It is not clear how N will accept every string. For example, M will run on all input of $\Sigma^*$ but only those strings that are in L(M) will be accepted and I don't understand how N will accept every input. Moreover, it is not clear why he choose string "0".

Note that I changed step 2 where Sipser wrote: "Run M in parallel on all strings in $\Sigma^*$" since as I believe mean the same thing unless you have something to say.

$\endgroup$
4
$\begingroup$

First, note that Sipser says ""If M's language isn't empty, N will accept every input".


Let us first prove this statement: Assume $L(M) \neq \emptyset$.

Then there exists some $x \in L(M)$. Because $L(M) \subseteq \Sigma^*$ we have $x \in \Sigma^*$. Then because $s_i \in \Sigma^*$ and $\Sigma^*=\{s_0, s_1, s_2, .... \}$, there exists an $i^*$ such that $s_{i^*} = x$.

The TM $N$ accepts "if M accepts any of these strings". Because $s_{i^*}$ is one of these strings, $N$ accepts.


Note that $N$ never considered its own input! It only decides whether to accept or not based on $M$ which is part of the TM $N$ itself, not $N$'s input.

The string 0 is totally arbitrary. You can pick any string because we know that $N$ will accept any string if and only if* the language of $M$ is not empty. Because we want to reduce to $T^{A_{TM}}$ this is indeed all we care for.

* The other direction remains to be shown for a complete proof.

$\endgroup$
7
  • $\begingroup$ Thank you Idmean, so If M's language isn't empty, it does accept only those strings that are membership of L(M) but not all strings of $\Sigma^*$ (since in Sipser's words that says N will accept every input means to me that L(M) = $\Sigma^*$). $\endgroup$
    – user777
    Jul 7 at 13:34
  • $\begingroup$ Now, you said that N accepts if M accepts any of these strings (the strings that are in L(M) but not all strings in $\Sigma^*$). Now, how this would imply "N will accept any string iff language of M is not empty"? $\endgroup$
    – user777
    Jul 7 at 13:40
  • $\begingroup$ Maybe his phrasing is confusing, but Sipser certainly didn't mean to imply $L(M) = \Sigma^*$. Concerning "N will accept any string iff language of M is not empty": I proved the forward direction in the answer. Is there something unclear about the proof itself? Or are you asking about the other direction? $\endgroup$
    – idmean
    Jul 7 at 13:48
  • $\begingroup$ Another hint that may clear up some confusion: Consider again that $N$ never uses its input in any way. It doesn't even need to read it. $\endgroup$
    – idmean
    Jul 7 at 13:50
  • $\begingroup$ Yes, I have a question. For example, why we choose string 0? Suppose M is a TM that decides all strings that are starting with 1. Now L(M) = {1, 10, 11, 100, ...}. Now If we plug this M into $T^{A_{TM}}$, then $T^{A_{TM}}$ in step 2 will say No, since N on input 0 doesn't accept (reject/loop). This imply that the oracle will return NO. Therefore, $T^{A_{TM}}$ accepts. This means that M's language is empty. Now can you tell me what went wrong? $\endgroup$
    – user777
    Jul 7 at 13:58

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.