2
$\begingroup$

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.

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

1 Answer 1

7
$\begingroup$

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.

$\endgroup$

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.