2
$\begingroup$

Can a Turing machine $M_A$ determine if the Turing machine $M_B$ accepts the set $W_k$?

I am curious about the answer to this as I am thinking about using the truth value of it on using it for a recursive enumerability proof.

$\endgroup$
  • 2
    $\begingroup$ Try $W_k = \emptyset$. Is it decidable whether the language of a Turing machine is empty or not? $\endgroup$ – Yuval Filmus Feb 9 '17 at 9:24
  • $\begingroup$ Interesting recursive idea. $\endgroup$ – wogsland Feb 12 '17 at 4:40
  • 1
    $\begingroup$ Wait... there seems some ambiguity. Do you mean $M_B$ accepts and only accepts $W_k$? $\endgroup$ – xskxzr Mar 23 '18 at 2:14
  • $\begingroup$ Now I have added an answer to handle $L(M_B)\supseteq W_k$. Maybe one can edit this question to make it more general. $\endgroup$ – xskxzr Mar 23 '18 at 4:25
  • 1
    $\begingroup$ Ultimately, the answer is "no" but, in any case, how do you propose to encode $W_k$ as a string to give it as an input to $M_A$? If $W_k$ is finite, it's easy, but what if it isn't. (Also, what's the parameter $k$ supposed to be?) $\endgroup$ – David Richerby Mar 23 '18 at 8:53
2
$\begingroup$

Is the language of all machines that accept $W$ recognizable?

$$L_W = \{\langle M\rangle : L(M) = W\}$$

The answer is unfortunately no, except in trivial cases. If $W$ is unrecognizable, then $L_W$ is empty (no machine recognizes $W$) and hence decidable (The machine that rejects all inputs decides $L_W$). In all other cases, $L_W$ is unrecognizable. We can show this using reductions from the unrecognizable rejection problem— the problem of determining whether a machine rejects a word.

  • If $W=\Sigma^*$, the set of all strings, then $L_W$ is unrecognizable (a standard result: "$M_x(w)$ simulates $M$ on $x$ for $|w|$ steps and accepts if the simulation doesn't accept by then." provides a reduction from the problem of deciding whether $M$ rejects $x$).
  • If $W\neq \Sigma^*$ is decidable, then $L_W$ is unrecognizable. Consider a program that takes a machine and word $\langle N, x\rangle$ and builds a new machine $N_x(w)$. The new machine decides whether $w\in W$ and accepts if so. Otherwise, it simulates $N$ on $x$ and does what it does. The machine $N_x$ therefore accepts $W$ (if $N$ rejects $x$) or all strings (if $N$ accepts $x$).

    If we could recognize whether $N_x$ accepts $W$ or not, we could recognize whether $N$ rejects $x$ or not—an impossibility.

  • If $W$ is recognizable but undecidable, then $L_W$ is unrecognizable: Consider a program that takes a machine and word $\langle N, x\rangle$ and builds a new machine $N_x(w)$. The new machine simulates $N$ on $x$ for $|w|$ steps. If the simulation accepts in that time, the machine accepts. Otherwise, the machine tests whether $w\in W$ and does what it does.

    Hence $N_x$ accepts the union of $W$ and the set of all strings longer than the number of steps it takes for $N$ to accept $x$. If $N$ rejects $x$, $N_x$ recognizes $W$. If $N$ accepts $x$, $N_x$ recognizes additional words. (Note that because $W$ is undecidable, there must be arbitrarily long strings not in $W$. Otherwise, a DFA could decide $W$ by memorizing the short strings and using a length requirement for the long ones. Hence $N_x$ recognizes a strict superset of $W$ if $N$ accepts $x$.)

    If we could recognize whether $N_x$ accepts $W$ or not, we could recognize whether $N$ rejects $x$ or not—an impossibility.

$\endgroup$
  • $\begingroup$ @xskxzr I've strengthened the statement now. Rice's theorem can prove that languages are undecidable. I've proven that moreover the language is unrecognizable in all but trivial cases. $\endgroup$ – user326210 Mar 22 '18 at 22:23
  • $\begingroup$ @xskxzr Yes, in my dialect a machine can reject either by explicitly rejecting, or by failing to halt. I no longer use Rice's theorem in my answer because I have a stronger result about unrecognizability. $\endgroup$ – user326210 Mar 23 '18 at 4:04
1
$\begingroup$

While user326210's answer analyzes the language $\{\langle M\rangle\mid L(M)=W\}$, my answer analyzes the language $L_W=\{\langle M\rangle\mid L(M)\supseteq W\}$.

$W$ is an empty set

$L_W$ is the set of encodings of all TMs, thus decidable.

$W$ is a finite but not empty set

$L_W$ is undecidable but recognizable.

Suppose $L_W$ is decidable by $D_{L_W}$, we can build a decider $D_H$ using $D_{L_W}$ to solve halting problem. The decider $D_H$ works as follows:

On input $\langle \langle M\rangle, w\rangle$:

  1. Construct a TM $M'$ working on input $w'$ as follows:

    1. Run $M$ on $w$.

    2. If $w'\in W$ (recall that $W$ is finite), accept. Otherwise reject.

  2. Run $D_{L_W}$ on $\langle M'\rangle$.

  3. If $D_{L_W}$ accepts, accept. Otherwise reject.

We can see if $M$ halts on $w$, $M'$ accepts $w'$ if and only if $w'\in W$, which means $L(M')=W$. Otherwise, $M'$ accepts nothing. Therefore $D_{L_W}$ accepts $\langle M'\rangle$ if and only if $M$ halts on $w$, so $D_H$ is indeed a decider for halting problem. Hence $L_W$ is undecidable by contradiction.

To recognize $W$, a TM can run $M$ on all strings in $W$ (recall again that $W$ is finite) and accepts if $M$ accepts all these strings. This TM recognizes $L_W$.

$W$ is an infinite set

$L_W$ is unrecognizable.

Suppose $L_W$ is recognizable by $M_{L_W}$, we can build a recognizer $M_R$ using $M_{L_W}$ to recognize $\overline{A_{\mathrm{TM}}}=\{\langle\langle M\rangle,w\rangle\mid M\text{ does not accept }w\}$, which is unrecognizable. $M_R$ works as follows.

On input $\langle \langle M\rangle, w\rangle$:

  1. Construct a TM $M'$ working on input $w'$ as follows:

    1. Run $M$ on $w$ with at most $|w'|$ steps.

    2. If $M$ accepts, reject. Otherwise accept.

  2. Run $M_{L_W}$ on $\langle M'\rangle$.

  3. If $M_{L_W}$ accepts, accept. If $M_{L_W}$ rejects, reject.

We can see if $M$ accepts $w$, say with $n$ steps, then $M'$ accepts $w'$ if and only if $|w'|<n$, which means $L(M')$ cannot be a superset of $L_W$ (recall that $L_W$ is infinite). Otherwise $M$ accepts every string, which means $L(M')$ is certainly a superset of $L_W$. Therefore $M_{L_W}$ accepts $\langle M'\rangle$ if and only if $M$ does not accept $w$, so $M_R$ is indeed a recognizer of $\overline{A_{\mathrm{TM}}}$. Hence $L_W$ is unrecognizable by contradiction.

$\endgroup$

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.