I read that Rice theorem applicable only for language property not for machine property. But today I have read from stack exchange and one site they are applying Rice theorem on machine also. My question is could we for both or language only?

  • 1
    $\begingroup$ Your question is very vague. Could you link to the "stack exchange and one site"? Also, don't forget that answers in Stack Overflow and other sites on theory of computation tend to be wrong, since they are given by people who are not experts. $\endgroup$ Oct 13 '21 at 8:30
  • $\begingroup$ @Yuval See this $\endgroup$
    – Punia
    Oct 13 '21 at 8:55
  • 2
    $\begingroup$ Rice's theorem is just one way of showing that a language is not decidable. There could be other ways. $\endgroup$ Oct 13 '21 at 10:00
  • $\begingroup$ Rice's theorem states that if $P$ is any property of languages satisfies some nontriviality property, then the language of Turing machines computing a language is $P$ is undecidable. If your language is of this form, then you can apply Rice's theorem to conclude that it is undecidable. If it isn't, then you cannot. $\endgroup$ Oct 13 '21 at 10:02
  • $\begingroup$ @Yuval I have shared the link, the answer is wrong? $\endgroup$
    – Punia
    Oct 13 '21 at 10:06

Let's start by formulating Rice's theorem.

Fix an alphabet $\Sigma$. We consider Turing machines that recognize languages over $\Sigma$ (the language recognized by a Turing machine consists of all inputs on which the Turing machine halts).

A collection $p$ of languages over $\Sigma$ is nontrivial if

  1. $L(M_1) \in p$ for some Turing machine $M_1$.
  2. $L(M_2) \notin p$ for some Turing machine $M_2$.

Theorem. If $p$ is non-trivial then $\{ M : L(M) \in p \}$ is undecidable.

The question you link to mentions two different languages. The first language $L_1$ is described extremely vaguely. One possible interpretation, inspired by the OP's vague comments, is that $L_1$ consists of all Turing machines $M$ for which there exists an input $x$ such that when running $M$ on $x$, the symbol $\sigma$ gets printed on the tape.

The second language $L_2$ is described more concretely, even though some vagueness still remains. It consists of all Turing machines $M$ such that for all integers $x,y$, if we run $M$ on input $\langle x,y \rangle$ then $M$ halts and outputs $\langle xy \rangle$; here $\langle xy \rangle$ is the encoding of the integer $xy$ according to some fixed encoding scheme, and $\langle x,y \rangle$ is similarly the encoding of the pair of integers $x,y$.

As you can see, none of the two languages are of the form considered by Rice's theorem. One of the answers mentions an extension of Rice's theorem which captures $L_2$, but doesn't provide any more details.

We can show that $L_1$ is undecidable by reduction from the halting problem. Given a Turing machine $M$, construct a Turing machine $M'$ which erases its input, simulates $M$, and prints $\sigma$ once $M$ halts (we arrange that $M$ never uses the symbol $\sigma$). Then $M$ halts iff $M' \in L_1$.

We can also show that $L_2$ is undecidable by reduction from the halting problem. Given a Turing machine $M$, construct a Turing machine $M'$ which runs $M$ on a parallel empty tape, and once it halts, checks whether the input to $M'$ is of the form $\langle x,y \rangle$, and if so, computes $\langle xy \rangle$ (otherwise we don't care what $M'$ does; it can just immediately halt). Then $M$ halts iff $M' \in L_2$.


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.