# Can a Turing machine determine if a set is accepted by a another Turing machine?

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.

• Try $W_k = \emptyset$. Is it decidable whether the language of a Turing machine is empty or not? Feb 9, 2017 at 9:24
• Interesting recursive idea. Feb 12, 2017 at 4:40
• Wait... there seems some ambiguity. Do you mean $M_B$ accepts and only accepts $W_k$? Mar 23, 2018 at 2:14
• 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. Mar 23, 2018 at 4:25
• 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?) Mar 23, 2018 at 8:53

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.

• @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. Mar 22, 2018 at 22:23
• @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. Mar 23, 2018 at 4:04

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.