1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ And where do you use Rice's theorem? Also, your question does not seem to fit with the language definition; what is the role of $p$ vs $P$? I'd guess you have a problem with some of the notation/definitions; best revisit them. Please clarify the question in case the problem persists. $\endgroup$ – Raphael♦ May 23 '14 at 6:31
  • $\begingroup$ I got the impression from page 29 of users.uoa.gr/~sdi0600297/Thewria%20Ypologismou/lecture16.pdf , but it seamed hard to believe, and to verify, so I wanted to ensure I am not misunderstanding the slide, or to correct my understanding if I am. $\endgroup$ – user16480 May 23 '14 at 10:08
  • $\begingroup$ You're misunderstanding something: "$p\in P(L(M))$" doesn't make sense. What is $P(L(M))$? Do you mean to define $L_P = \{\langle M\rangle \mid L(M)\text{ has property }P\}$? $\endgroup$ – David Richerby May 25 '14 at 2:22
  • $\begingroup$ $P(L(M))$ is the set of properties of the language of the Turing machine M. So $p \in P(L(M))$ means that $L(M)$ has property $p$. $\endgroup$ – user16480 May 25 '14 at 5:17
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I suppose you could design an encoding that converts the description of a Turing Machine into any string. Then $L_p$ is also the set of all strings correct. And the basis is that L(M) is always recursively enumerable because M is a machine that enumerates it? $\endgroup$ – user16480 May 23 '14 at 17:13
0
$\begingroup$

Not sure if I understood your question correctly, but if $P$ is a trivial property, i.e., shared by all languages in $RE$, then $HALT$ language also has that property. So, $L$ in your definition could just as easily be $HALT$; it fits your definition. But, $HALT$ is not decidable. Hence, the answer is no.

Improve this answer
$\endgroup$
1
0
$\begingroup$

In Rice's theorem, a 'trivial property' is a property that holds for all subprograms (partially computable functions) within a specific language.

If this is what you intended, then the answer to your question is: no, the presence of a trivial property does not mean a specific language is decidable. However, such a property would necessarily be invariant - such as memory safety, purity, or deadlock freedom. Naturally, a program with a non-terminating expansion cannot have any trivial inductive properties that are functions of said expansion.

If you truly mean a trivial property as one possessed by all recursively enumerable languages, then I hypothesize that the only such properties are those directly implied by being recursively enumerable languages, and that also does not imply decidability.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy