Rice theorem

Question

s

Rice theorem says any non-trivial property of a language is Undecidable. Then how is above one REL.

Does it mean we cannot say anything for a trivial property?

Comments

I guess here it means.. as it's the trivial property ... it makes the language decidable so it's Recurisve and every recursive is also recursive enumerable.

---

Does every trivial property decidable?

---

As trivial property is something that is true for all TM's.. so it should be always be decidable.
Rest lets see what arjun sir say.. I always get confused in TM's..

Answer 1

Well, what is trivial? It is something which is TRIVIAL. Which means it is trivial.

:) It is so hard to define trivial because it is so trivial. Something which is so true or known - like Earth having water. In set theory, if all elements of a set has a property or no element has it, that property becomes trivial. Now, for decidability, we deal with if a particular element satisfies a given property or not. For trivial properties, decidability also becomes trivial as there is no need to check if an element satisfies it or not - either all of them satisfies or none satisfies. So, all trivial properties are trivially decidable.

2 points about Rice's theorem here:

Any non-trivial property of recursively enumerable languages is undecidable. (Trivial property is decidable)

Any non-monotonic property of recursively enumerable set is not even semi-decidable. But monotonic property may or may not be semi-decidable.

Comments

@thor But there are infinite even numbers- when to stop dovetailing?

@Reena It is not r.e. Should have a reduction from non r.e. language.

@Akriti yes.

---

U mentioned "Trivial property is decidable".

We know decidable means recursive.

so the ans for this question should be more appropriately set of RECURSIVE.

---

@Arjun above mentioned L in comments is RE ?? BECAUSE we have EP for this.