# 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? – Yuval Filmus Feb 9 '17 at 9:24
• Interesting recursive idea. – wogsland Feb 12 '17 at 4:40
• Wait... there seems some ambiguity. Do you mean $M_B$ accepts and only accepts $W_k$? – xskxzr Mar 23 '18 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. – xskxzr Mar 23 '18 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?) – David Richerby Mar 23 '18 at 8:53

## 2 Answers

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. – user326210 Mar 22 '18 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. – user326210 Mar 23 '18 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.