[Solved]: Is $L_p$ decidable when p is a trivial property?

Problem Detail: 

If

$\qquad\displaystyle 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

1. $L_p$ is the set of all TM descriptions or
2. $L_p=\emptyset$.

In the first case, a decider for $L_p$ ignore the input $\langle M\rangle$ 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