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

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.

• I am sorry, but I do not get why you cannot apply Rice's Theorem in the first case, even if the language is different from the second one. – Leo163 Feb 19 '18 at 19:20
• Because there exists no TM whose language equals the totality problem as no TM can recognize the totality problem and therefore L* is empty and Rice's theorem is not applicable. But maybe I'm just being dumb. – blank Feb 19 '18 at 19:30

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.

• Hello, welcome to Computer Science! Thank you for your in depth discussion of the issues involved here, I personally much appreciate answers that go slightly further (and say more!) than what is actually asked (and answer what should have been asked!). I do hope you will continue to make good contributions like this one. Anyway, if you're up to a friendly chat once in a while, just drop by in the chatroom: Computer Science Chat and talk. – Discrete lizard Mar 21 '18 at 22:06

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.

• This means that S* is trivial because it's empty, thus L* is decidable. S' is a non-trivial subset of all the computable functions and therefore not decidable. Is that right? – blank Feb 19 '18 at 20:40
• I believe my answer speaks for itself. – Yuval Filmus Feb 19 '18 at 20:49