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?
-
$\begingroup$ Not really. Did you read my description? I wanted examples, not the definition. $\endgroup$– forkexecFeb 27, 2014 at 22:33
-
$\begingroup$ From the definition, it's clear that there are exactly two trivial properties ("everything" and "nothing"); everything else is non-trivial. $\endgroup$– David RicherbyFeb 27, 2014 at 22:38
-
$\begingroup$ I understand that part. I needed examples to get an intuition and Shaull's answer was helpful for that. Thanks anyway. $\endgroup$– forkexecFeb 27, 2014 at 22:44
-
$\begingroup$ This question is clearly not a duplicate of the question it has been marked as a duplicate of. $\endgroup$– doubleOrtJun 14, 2018 at 11:08
1 Answer
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.
-
$\begingroup$ No, a property is a set of languages. For example, it is decidable whether a Turing machine has exactly seventeen states (just check the description) but the set of Turing machines with exactly seventeen states is neither empty nor the set of all Turing machines. However, the class of languages that are accepted by some Turing machine with exactly 17 states is not undecidable by Rice's theorem. $\endgroup$ Feb 27, 2014 at 22:52
-
$\begingroup$ @DavidRicherby - you are talking about a semantic property. Indeed, Rice's theorem discusses semantic properties. However, a property need not refer to languages. For example, the set of TMs with 17 states is a syntactic property, and it is not undecidable by Rice's theorem (it is decidable). But there are syntactic properties that are undecidable. For example - the set of TMs that have a state that is never reached in any run. Rice's theorem gives us nothing, yet still the problem is undecidable. $\endgroup$– ShaullFeb 28, 2014 at 5:47
-
$\begingroup$ Is "no unreachable states" really a syntactic property? It seems to be about the behaviour of the machine, not its description. $\endgroup$ Feb 28, 2014 at 13:14
-
1$\begingroup$ The set of TMs with 17 states is of course, a decidable syntactic property (just count the states). The set of TMs whose language is recognizable by a 17 state TM is a semantic property (since two TMs with the same language either have or don't have this property). Anyway, I think the OP got what he wanted, and both of us know how to use Rice's theorem :) $\endgroup$– ShaullFeb 28, 2014 at 13:38
-
1$\begingroup$ $L(M)$ can be in co-RE, but it is always also in RE. That is, if it's in co-RE, then it's in fact in R. The reason is that by definition, a language of a Turing machine is recognizable (by that Turing machine). $\endgroup$– ShaullDec 23, 2017 at 9:24