Is the Rice's theorem applicable to $\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) = H_{all} \mbox{ } \}$?

Question

Until just now I thought that I have fully understood Rice's theorem but this example irritates me:

$L^* = \{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) = H_{all} \mbox{ } \}$ where $H_{all}$ denotes the totality problem. Correct me if I'm wrong but in my opinion this is not the same as $L' = \{ \langle M \rangle \mid M \mbox{ is a Turing machine that halts on every input} \mbox{ } \}$. Here, I could apply Rice's theorem and conclude that L' is not decidable but in the other case, L* is actually empty so the theorem is not helpful.

Answer 1

Well, Rice's theorem doesn't apply but we don't need it—$L^*$ is empty and therefore decidable.

To figure this out, we just need to be meticulous about what these languages are.

• $L^*$ is the set of all Turing machines that recognize the totality problem. It is the set of all Turing machines that can take in a Turing machine $\langle N\rangle$ and accept just if $N$ halts on all inputs.

• $L^\prime$ is the set of all Turing machines that halt on all inputs.

• They're different languages: $L^*$ is the set of all machines whose language is $L^\prime$.

The totality (all-halt) problem is unrecognizable: there is no Turing machine that takes in a TM $\langle N\rangle$ and accepts just if $N$ halts on all inputs. (Consider a reduction to the halting problem.) Therefore, $L^*$ is empty and $L^\prime$ is unrecognizable.

$L^*$ is empty, therefore decideable (when given a machine $\langle N\rangle$ and asked if it recognizes the totality problem, always say no.) $L^\prime$ is unrecognizable, which is stronger than merely undecidable.

But, if we didn't already know that $L^\prime$ was unrecognizable, we could use Rice's theorem to show that $L^\prime$ is undecidable. There's a string in $L^\prime$, for example the Turing machine that ignores its input and always accepts. There's a string not in $L^\prime$, for example the Turing machine that ignores its input and loops forever.

---

Also, a side note: Rice's theorem says that non-trivial language properties of TMs are undecideable. As you point out, there are two trivial languages which the theorem doesn't cover: the empty language $\varnothing$ and the language of all strings $\Sigma^*$. Note that we don't need Rice's theorem for these languages to determine decidability— we already know they're decideable. In fact, they're regular: there's a DFA that accepts all strings, and a DFA that accepts no strings.

Answer 2

Rice's theorem states that the problem of determining, given a Turing machine $M$, whether $L(M)$ belongs to some set of languages $S$ is decidable if and only if $S$ is trivial, that is, either $L(M) \in S$ for every Turing machine $M$, or $L(M) \notin S$ for every Turing machine $M$.

Hence all you need to do in order to determine whether $L^*,L'$ are decidable, is to determine whether the corresponding sets $S^*,S'$ are trivial or not.