Problem Detail: If $qquaddisplaystyle L_p = { langle M rangle : p in P(L(M)) text{ s.t. } p text{ is a specific trivial property} }$, where a trivial property is a property that is shared by all recursively enumerable languages or is not a property of any recursively enumerable language, is it implied that $L$ is decidable?
Asked By : tAllan
Answered By : Rick Decker
If $p$ is a trivial property of r.e. languages, it either applies to all r.e. languages or applies to no r.e. language. That means that either
- $L_p$ is the set of all TM descriptions or
- $L_p=emptyset$.
In the first case, a decider for $L_p$ ignore the input $langle Mrangle$ and immediately accept and in the second case, a decider would similarly reject. In either case, $L_p$ is clearly decidable. While we don’t necessarily know which decider is the right one to use, that doesn’t matter, since the existence of a decider is all that we need.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/26009 Ask a Question Download Related Notes/Documents
