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?


1 Answer 1


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

  • $\begingroup$ How may I find if the language is semi-decidable or non semi decidable? $\endgroup$ Commented Mar 1, 2015 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$ Commented Mar 1, 2015 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$ Commented Mar 1, 2015 at 16:55
  • 2
    $\begingroup$ See our reference question. $\endgroup$ Commented Mar 1, 2015 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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