# Does rice theorem applies to languages only or does it apply to machines as well?

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.

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

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.

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.