0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/Rice%27s_theorem#Proof_sketch $\endgroup$ – vadim123 Apr 27 '18 at 13:26
  • $\begingroup$ Can you state the theorem you're applying? Which of the premises are you not sure hold? $\endgroup$ – Henning Makholm Apr 27 '18 at 13:29
  • $\begingroup$ @vadim: That's a proof of the theorem itself, which is not what the question is asking for. $\endgroup$ – Henning Makholm Apr 27 '18 at 13:30
  • $\begingroup$ @HenningMakholm I'm not sure about the whole theorem really, nor how to apply it to this example. $\endgroup$ – lostAtLife Apr 27 '18 at 17:33
  • $\begingroup$ @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. $\endgroup$ – Henning Makholm Apr 27 '18 at 17:56

Your Answer

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

Browse other questions tagged or ask your own question.