-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Ran G. May 16 '15 at 22:59
  • $\begingroup$ Maybe this will help. Or search for other questions about Rice's theorem. $\endgroup$ – Ran G. May 16 '15 at 23:03
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.