# Type of undecidability in Rice Theorem

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

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

• How may I find if the language is semi-decidable or non semi decidable? – user2851298 Mar 1 '15 at 16:50
• 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. – David Richerby Mar 1 '15 at 16:53
• How do you prove the non computability of $\psi_p = x^2$? what method we may use to conclude the non-computability ? – user2851298 Mar 1 '15 at 16:55
• See our reference question. – David Richerby Mar 1 '15 at 16:57