5
$\begingroup$

I have to show a property P is trivial.

This problem has to do with Rice's Theorem, which I do not completely understand. Can someone explain the difference between trivial and non-trivial properties?

$\endgroup$
2
  • 1
    $\begingroup$ To understand Rice's theorem, see this question. $\endgroup$
    – Juho
    Commented Feb 6, 2014 at 20:26
  • $\begingroup$ this is actually fairly subtle and one way to study this is just looking at a long list of example properties that Rices thm covers, and those it doesnt apply to, and getting some intuition that way. it would be neat if someone wrote up an extended analysis of this somewhere in a paper etc, but have never seen one. $\endgroup$
    – vzn
    Commented May 6, 2014 at 16:11

2 Answers 2

13
$\begingroup$

A "trivial" property is one that holds either for all languages or for none.

$\endgroup$
3
  • $\begingroup$ So is there a common way of proving properties are trivial/non-trivial? Like reducing to the Accept problem for undecidability? $\endgroup$ Commented Feb 6, 2014 at 20:01
  • 4
    $\begingroup$ Nah. Usually you just give something that has the property and something that doesn't. $\endgroup$ Commented Feb 6, 2014 at 22:36
  • 2
    $\begingroup$ @AlexChumbley Usually, trivial properties (if stated simply) will be pretty clearly trivial. What do all languages have in common? They're countable sets of strings of finite length. If the property implies more than that, you're probably in undecidable territory. $\endgroup$
    – Patrick87
    Commented May 6, 2014 at 16:27
4
$\begingroup$

A "property" is simply a subset of languages in $RE$ -- the set of all the languages that "satisfy" that property. A non-trivial property $P$ is a non-empty set $P$ which is strictly contained in $RE$, that is $\emptyset \subset P\subset RE$. It means there is at least one RE language that doesn't satisfy $P$, and at least one RE language that does satisfy it.

Examples:

The property: "the language is finite." Formal definition: $P = \{ L \mid |L|<\infty\}$. This property is non-trivial.

The property: "The language can be recognized by a TM". Formally: $P=\{ L \mid \exists M \text{ s.t. } L=L(M)\}$. This property is trivial: in fact $P=RE$, that is, ALL RE languages satisfy it.

The property: "The language has a reduction from the non-halting problem". Formally: $P = \{ L \mid \overline{HP} \le L\} \cap RE$. This property is trivial: in fact, $P=\emptyset$.

$\endgroup$
2

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.