How do you classify properties as Trivial and Non-trivial?

Problem Detail: 

I understand what Rice's theorem states and what Trivial and Non-trivial properties mean. However, when given some property, I am having a hard time seeing if it is Trivial or Non-trivial. Can someone help me understand this better, maybe with some good examples?

Asked By : forkexec

Answered By : Shaull

A property $P$ is a set of Turing machines. The property is trivial if it contains every TM, or if it is empty.

Essentially, in order to check if a property is trivial, just check if there is a TM that satisfies it and if there is a TM that does not satisfy it. If both kinds exist, then the property is nontrivial. Otherwise it is trivial.

However, deciding this can be difficult...

For example, consider the property $\{M: L(M)=\emptyset\}$. This is a non-trivial property, since there are TMs with an empty language, and there are TMs with a nonempty language.

A trickier example is $\{M: L(M)\in RE\}$. Initially, this may seem like a nontrivial property. But recall that every TM recognizes its own language. So $L(M)$ is in RE for every $M$. Thus, this property is simply the collection of every TM. So it is trivial.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22106