Rice Theorem in Theory of computation

 

Rice Theorem in Theory of computation

Any non-trivial property of the language recognizable by a turing machine is undecidable.

Property of a language

Trivial property

A property that holds for every machine.

Non trivial Property

A property that is neither true nor false for every computable function.

For a property of recursive enumerable set to be non trivial there should exist at least recursive enumerable languages hence two Turing machine the property holding for one and not holding for other.

Thus rice theorem the language describing any non trivial property of turing machine is not recursive.

Any trivial property is always decidable because the decision is known ahead and that is why property is trivial.

Example

L(M) has at least 10 string

we can have t(yes) for Σ*  and T(no) for Ø. Hence L={M|L(M) has at least 10 string is not turing decidable.

Example

L(M) is Finite.

We have T(yes) for Ø and T(no) for  Σ*.Hence not turing recognizable.

Example

L(M)={0}.

T(yes) for {0} and T(no) for Σ*.Hence is not turing recognizable.

Example

L(M) is regular.

T(yes) for Ø and T(no) for non-regular language is not turing recognizable.