World's most popular travel blog for travel bloggers.

Rice Theorem - What is non-trivial property?

, , No Comments
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

0 comments:

Post a Comment

Let us know your responses and feedback