1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Leo163 Feb 19 '18 at 19:20
  • $\begingroup$ 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. $\endgroup$ – blank Feb 19 '18 at 19:30
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Discrete lizard Mar 21 '18 at 22:06
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – blank Feb 19 '18 at 20:40
  • $\begingroup$ I believe my answer speaks for itself. $\endgroup$ – Yuval Filmus Feb 19 '18 at 20:49

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.