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.

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

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.


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.