# Is a language of TMs undecidable using Rice's theorem

Given a language: $A = \{ <M> | M\ rejects\ the\ string\ "101" \}$

Can I prove it is undecidable using Rice's theorem?

See like the theorem conditions are met (there exists non trivial language that describes the machine language )

• Do you mean "undecidable"? (Rice's theorem shows undecidability, not decidability). – Shaull May 15 '17 at 11:20
• Yes - fixed now. – Homem Gustavo May 15 '17 at 11:22
• So, if you think the conditions are met - what's the question? – Shaull May 15 '17 at 11:31
• I know that you cannot apply rice theorem when a machine constrain is set (in this case , the machine must reject) is it true? Is the proof ok? – Homem Gustavo May 15 '17 at 11:42
• Just check whether or not the conditions of Rice's theorem hold. There's nothing more to it. – David Richerby May 15 '17 at 12:46

A semantic property of TMs is a set of TMs $P$ such that for every two TMs $M_1,M_2$, if $L(M_1)=L(M_2)$ then either $M_1,M_2\in P$ or $M_1,M_2\notin P$. That is, membership in $P$ is determined only by the language, and not by the "inner workings" of the machine.