Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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".
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.
