1
$\begingroup$

I have seen 2 answers in stackoverflow:

  1. A "trivial" property is one that holds either for all languages or for none.

  2. The property is trivial if it contains every TM, or if it is empty.

My problem is: Saying that a property is trivial if it contains every TM is not the same as saying that a property is trivial if it contain all the languages (including non RE languages).

Same as for: Saying that a property is trivial if it is does not contain any TM languages is not the same as saying that a property is trivial if it is empty.

Improve this question
$\endgroup$
3
  • $\begingroup$ Have you read the comments under the second answer you link? You are right, it's not the same thing, and they don't claim that (but wrote the post in a potentially confusing way.) $\endgroup$
    – Raphael
    Aug 31, 2017 at 18:16
  • $\begingroup$ Then what is the currect definition? $\endgroup$
    – Stav Alfi
    Aug 31, 2017 at 18:25
  • 1
    $\begingroup$ I find the comments rather clear about that: the first. But that said, there are probably many equivalent definitions. Definitions are never "correct", there are only more or less useful. $\endgroup$
    – Raphael
    Aug 31, 2017 at 18:25

1 Answer 1

Reset to default
2
$\begingroup$

We call a set of languages, $P\subseteq 2^{\Sigma^*}$, a property. If you think of this subset as the set of languages who satisfy some property, then we can simply say that a language $L$ satisfies the property iff $L\in P$.

Rice theorem tells you that you can't, given a Turing machine $M$, check if $L(M)$ satisfies some non trivial property $P$, i.e. $P\neq \emptyset$, $P\nsupseteq RE$. Note that Shaull makes a distinction between semantic and syntactic properties in the comments. To the best of my knowledge, the standard definition of a property in the context of Rice's theorem is a set of languages.

Improve this answer
$\endgroup$
9
  • $\begingroup$ courses.engr.illinois.edu/cs373/sp2013/Lectures/lec25.pdf - Definition 3 - You are saying something complitly different. $\endgroup$
    – Stav Alfi
    Aug 31, 2017 at 18:24
  • $\begingroup$ FWIW, it's also common to express properties as predicates, i.e. boolean-valued functions (here of type $\Sigma^* \to \{0,1\}$). This is clearly equivalent, since subsets and indicator functions identify uniquely. $\endgroup$
    – Raphael
    Aug 31, 2017 at 18:27
  • $\begingroup$ @StavAlfi How so? I don't see it. (I think you need some time learning how to read mathematics. I can recommend the Book of Proof, which is available for free.) $\endgroup$
    – Raphael
    Aug 31, 2017 at 18:28
  • $\begingroup$ Saying that a property is trivial if it contains every TM is not the same as saying that a property is trivial if it contain all the languages (including non RE languages)...... $\endgroup$
    – Stav Alfi
    Aug 31, 2017 at 18:29
  • $\begingroup$ Each TM has a corresponding language. So if it contains every TM, then it contains every language. $\endgroup$
    – rus9384
    Aug 31, 2017 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.