patternMinor
What's a trivial property?
Viewed 0 times
trivialpropertywhat
Problem
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?
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#21398, answer score: 4
Revisions (0)
No revisions yet.