1
$\begingroup$

This question already has an answer here:

Every nontrivial property of the recursively enumerable languages is undecidable.

What exactly is nontrivial property?

$\endgroup$

marked as duplicate by Raphael Jan 7 '14 at 7:58

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    $\begingroup$ A property that holds for every machine or holds for none is trivial. Rice's theorem does not apply to such a property. $\endgroup$ – Untitled Jan 6 '14 at 14:48
  • 1
    $\begingroup$ @Untitled: please make this an answer. $\endgroup$ – Patrick87 Jan 6 '14 at 17:06
  • 2
    $\begingroup$ For example, the Wikipedia page on Rice's theorem explains this at least twice. You are expected to research the problem on your own before posting here. If you did research it on your own, let us know what you looked at and what you didn't understand, so we can give more specific help. $\endgroup$ – David Richerby Jan 6 '14 at 17:06
  • $\begingroup$ This a place for questions that can not (easily) be answered by searching Wikipedia or opening a textbook. Also, we have the answer on here already. (Also, your problem illustrates why explanations in "simple English" should never be given/read alone when it comes to TCS.) $\endgroup$ – Raphael Jan 7 '14 at 7:59
5
$\begingroup$

A property that holds for every machine or holds for none is trivial. Rice's theorem does not apply to such a property.

To see why, note that such a property can be decided by a very simple Turing machine, which accepts/rejects every Turing machine representation.

$\endgroup$

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