# Application of Rice's Theorem

How can I prove, by applying Rice's theorem, that the language L is undecidable?

$L = \lbrace \alpha : M_{\alpha}(x) =x^2 \,\,\, \forall x \in \lbrace 0,1\rbrace^* \rbrace$

I think this is a direct application but I don't fully understand the theorem, nor how to formally write out the answer.

In my notes I have Rice's theorem written as: Let $R$ be the set of all functions of the form $f:\lbrace 0,1 \rbrace^* \rightarrow \lbrace 0,1 \rbrace^* \cup \lbrace \perp \rbrace$ where $\perp$ means that the Turing machine does not halt. Then let $C$ be a non-empty proper subset of $R$. Then the language $\lbrace \alpha : M_{\alpha}$ corresponds to a function $f \in C \rbrace$ is undecidable.

• en.wikipedia.org/wiki/Rice%27s_theorem#Proof_sketch – vadim123 Apr 27 '18 at 13:26
• Can you state the theorem you're applying? Which of the premises are you not sure hold? – Henning Makholm Apr 27 '18 at 13:29
• @vadim: That's a proof of the theorem itself, which is not what the question is asking for. – Henning Makholm Apr 27 '18 at 13:30
• @HenningMakholm I'm not sure about the whole theorem really, nor how to apply it to this example. – lostAtLife Apr 27 '18 at 17:33
• @lostAtLife: The first step is to find out what the theorem says, then. Do you have a statement of it in your textbook. Find it and quote it in your question. – Henning Makholm Apr 27 '18 at 17:56