2
$\begingroup$

Rice theorem says that any non trivial property of a language recognized by a Turing Machine is undecidable.

Now does this theorem applies to machines as well since we can define a language consisting of strings which are encoding of machines?

For example whether a machine will run more than 100 steps on some input? This is nontrivial but wikipedia says it is decidable.

$\endgroup$
  • $\begingroup$ "Rice theorem says that any non trivial property of a language recognized by a Turing Machine is undecidable." -- no, it doesn't. $\endgroup$ – Raphael Oct 30 '17 at 13:44
  • $\begingroup$ Related questions: one, two. $\endgroup$ – Raphael Oct 30 '17 at 13:46
  • $\begingroup$ @Raphael what is wrong with the statement? What's the correct statement? $\endgroup$ – Kishan Kumar Oct 30 '17 at 18:04
  • $\begingroup$ Rice's theorem makes a statement about certain sets of (numbers of) Turing machines. $\endgroup$ – Raphael Oct 31 '17 at 14:59
1
$\begingroup$

The Rice's theorem can also be stated in terms of index sets of TMs.

Lets start with a basic definition of a property of a language. A property of a language is a set of languages. For example $$P_{reg} = \{L \mid L \text{ is regular } \}$$ and $$P_{fin} = \{L \mid L \text{ is finite } \}$$ are properties of languages.

We also define a language of indexes as $$L_P = \{\langle M \rangle\ \mid L(M) \in P\}$$ In simple words, a set of TM indexes such that the language recognized by $M$ belongs to the property $P$. Now, the Rice's theorem states that if $P$ is nontrivial then the problem whether $n \in L_P$ is undecidable, i.e., $L_P$ is undecidable.

However, we cannot apply it to the following sets $$L_1 = \{\langle M \rangle\ \mid M \text { has } 5 \text{ states} \}$$ and $$L_2 = \{\langle M \rangle\ \mid M \text { never writes to the tape} \}$$ since they talk about properties of Turing machines and not languages (we cannot say a language $L$ has 5 states). They may be decidable or not which may be proved the other way (not using the Rice's theorem). For example, $L_1$ is decidable since you simply count the number of states of a TM.

So, the answer to your question

does this theorem applies to machines

depends on what set of TMs you are talking about. If this is a set of TMs whose recognizing languages belong to some nontrivial property of a language then the answer is "yes", otherwise the answer is "no".

$\endgroup$
0
$\begingroup$

Rice's theorem talks about the decision problem associated to a set of computable functions. There isn't a unique correspondence between computable functions and Turing machines, consider for example a machine that always returns $YES$ and a machine that does nothing for 100 steps and then returns $YES$.

You may apply Rice's theorem to a set of machines $S$ if $S$ is such that for all $x, y$:

$\qquad (M_x \in S \wedge \phi_x = \phi_y) \rightarrow M_y \in S$

where $M_z$ is the $z$-th Turing machine in any Goedelization and $\phi_z$ is the function computed by the $z$-th Turing machine.

$\endgroup$

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.