# Use Rice's theorem to prove the following is undecidable

Given the language $L=\{\alpha \mid M_{\alpha}(x)=x^3$ for all $x\in\{0,1\}^*\}$. Prove using Rice's theorem that $L$ is undecidable.

Rice's theorem: Let $P$ be a set of all computable functions $f:\{0,1\}^*\rightarrow \{0,1\}^*$(i.e all functions which have a corresponding turing machine $M$, such that $M(x)=f(x)$). Let $C\subseteq P$, where $C\neq\emptyset$. Then deciding if a turing machine $M$corresponds to a function $f\in C$, is an undecidable problem.

So I need to show that deciding if a string $x$ is in $L$, is equivalent to deciding if a function $f\in C$, where $C\subseteq P$. But I don't even know where to begin with showing this.

• it's unclear to me what you are asking. Rice's theorem states exactly what you need. You just need to show it's condition hold. Do you agree? – Ran G. May 16 '15 at 22:59
• Maybe this will help. Or search for other questions about Rice's theorem. – Ran G. May 16 '15 at 23:03

I believe Rice's Theorem also needs $C$ to be actually different from $P$, otherwise, it is also a trivial property.
In your case, you have a property of recursively enumerable languages, and you need to show it is not trivial. To do so, you just need to find a Turing Machine that doesn't belong to $L$, and one that does.