Rice theorem says every non-trivial property of languages of Turing machines is

Question

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|?x is defined for at least one input}

and also this non-r.e. language as well:

?p=x2

There is no algorithm to determine ?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?

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.