# What is the meaning of undecidability in Rice Theorem?

Rice theorem says every non-trivial property of languages of Turing machines is undecidable. what is the meaning of undecidability here? is it semi-decidable?

As an example the following language is R.E but it contains a non-trivial property

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

this language equals to $Empty$ $Complement$ and it is clearly r.e.(m-complete in fact) while non-emptiness property is non-trivial.

• It means the same as everywhere else (in computability theory). – Raphael Feb 27 '15 at 7:35

## 1 Answer

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

To see that an undecidable problem is not necessarily semi-decidable, observe that there are uncountably many problems but, since each decidable or semi-decidable problem corresponds to a Turing machine, there are only countably many decidable and semi-decidable problems.