edited by
1,293 views
5 votes
5 votes

What is the difference between Non-trivial property (in 1st theorem)and Non-monotonic property ( in 2nd theorem)?

I was going through Rice's theorem but unable to differentiate between these 2 properties.Please give the detail to differentiate both 

For a property to be non-trivial, there should exist at least two Turing machines, the property holding for the language of one (Tyes) and not holding for the language of other (Tno)

For a property to be non-monotonic, there should exist at least two Turing machines, the property holding for the language of one (Tyes) and not holding for the language of other (Tno) and  L(Tyes)⊂L(Tno)​​​​​​​

Source: http://gatecse.in/rices-theorem/

edited by

1 Answer

Best answer
5 votes
5 votes
  • $P$ is $R.E.$ language property
  • If no R.E. language satisfies P then P will be called a trivial property.
  • If ALL R.E. language satisfies P then also P will be called a trivial property.
  • Other than this P is Non-trivial.
  • Now, 
  • If language $L$ satisfies a R.E. property P, then $\rightarrow$
  • If all supersets of $L$ also satisfy the property $P$.
  • Such $R.E.$ language property is called monotone property. monotone may not be trivial or may be trivial.
  • Example Monotone Property($P$) : "acceptance of at least string "$ab$" over alphabet $(a+b)^{*}$ "
  • Failure of this ALL superset satisfiability of P means P is non-monotone.
  • Non-Monotonic property language is NOT-RE.
  • Corresponding Property SET (S) for a Non-Monotonic property is not NULL. (because we are assuming some L satisfies P but supersets of L not satisfy ). S can not be a set of ALL RE also.So, a Non-Montonic property is also not trivial. 
selected by

Related questions

1 votes
1 votes
0 answers
1
Sumaiya23 asked Jan 23, 2018
428 views
What is monotonic and non-monotonic property. Please explain the second postulate of Rice's Theorem.