Cheap and Secure Web Hosting Provider : See Now

[Solved]: Use Rice's theorem to prove the following is undecidable

, , No Comments
Problem Detail: 

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.

Asked By : Andrew Brick

Answered By : Théo Winterhalter

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42649

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback