1
$\begingroup$

Rice's theorem: Any nontrivial property about the language recognized by a Turing machine is undecidable.

I know the proof but I am not able to understand the theorem. I think trivial properties are like :language recognised by Turing machine contain at substring "aab". where as nontrivial property means is language accepted by Turing machine is finite etc.

My question : Give at least two example of trivial properties and two non-trivial property about the language recognized by a Turing machine.

$\endgroup$

1 Answer 1

1
$\begingroup$

In the context of Rice's theorem, a trivial property has a very specific meaning.

Here, we define a property to be a set of Turing-recognizable languages. A property is non-trivial unless it contains no languages, or contains all Turing-recognizable languages.

We can clearly recognize these with a Turing Machine, since we can just make a machine that always says "YES" for the first case, or make a machine that always says "NO" for the second.

So both the properties you have identified are non-trivial properties, and are thus undecidable by Rice's theorem.

$\endgroup$

Your Answer

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

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