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
