4
$\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$
  • 1
    $\begingroup$ To understand Rice's theorem, see this question. $\endgroup$ – Juho Feb 6 '14 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 May 6 '14 at 16:11
12
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So is there a common way of proving properties are trivial/non-trivial? Like reducing to the Accept problem for undecidability? $\endgroup$ – Alex Chumbley Feb 6 '14 at 20:01
  • 4
    $\begingroup$ Nah. Usually you just give something that has the property and something that doesn't. $\endgroup$ – Dennis Meng Feb 6 '14 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 May 6 '14 at 16:27
3
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.