1
$\begingroup$

Rice theorem says every non-trivial property of languages of Turing machines is undecidable. As David Richerby said in here :

Undecidable means not decidable. Undecidable problems may or may not be semi-decidable.

I would like to know how to find out Rice Theorem leads to semi-decidability or non-semi-decidability?

As an example Rice Theorem is applicable to this r.e. language

$A = \{x | \phi_x$ is defined for at least one input$ \}$

and also this non-r.e. language as well:

$\psi_p = x^2$

There is no algorithm to determine $\psi_p$ has that property at all while for $A$ we can simply run the program forever an see whether it accepts one input or not. I would like to know using Rice Theorem is there any way to determine this difference?

$\endgroup$
2
$\begingroup$

Rice's Theorem just says it's undecidable. Some undecidable languages are semi-decidable; some (almost all, in fact) of them aren't.

$\endgroup$
  • $\begingroup$ How may I find if the language is semi-decidable or non semi decidable? $\endgroup$ – user2851298 Mar 1 '15 at 16:50
  • 1
    $\begingroup$ You have to use your brain and figure it out on a case-by-case basis. There's no recipe that always works -- that's exactly what it means for something to be undecidable. $\endgroup$ – David Richerby Mar 1 '15 at 16:53
  • $\begingroup$ How do you prove the non computability of $\psi_p = x^2$? what method we may use to conclude the non-computability ? $\endgroup$ – user2851298 Mar 1 '15 at 16:55
  • 2
    $\begingroup$ See our reference question. $\endgroup$ – David Richerby Mar 1 '15 at 16:57

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.