Problem Detail: Every nontrivial property of the recursively enumerable languages is undecidable. What exactly is nontrivial property?
Asked By : Alvar
Answered By : Untitled
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/19536
