World's most popular travel blog for travel bloggers.

[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 :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback