What is Rice theorem?

According to Rice's theorem Undecidability is not an exception it is the rule followed by unrestricted grammar. It states that any nontrivial property of a recursively enumerable language is undecidable.

Rice Theorem :

The Rice theorem states the following.

Let P be a non-trivial property of Turing recognizable languages. The problem "does L(M) has the property P?" is undecidable.

In other words, it can be said that ‘any non-trivial property about the language recognized by a Turing machine is undecidable.’

Before discussing the theorem, we need to discuss two important definitions, namely ‘property’ , ‘Trivial’ and ‘non-trivial property’.

·        Property: Let P be an arbitrary class of Turing recognizable language. P is called a property of L if L ∈ P.

·        Non-Trivial Property: Let P be a property of Turing recognizable language. The property P is said to be non-trivial if there exists L 1 and L2, two Turing recognizable languages such that L1 ∈ P but L2 ∉ P.

·        Trivial Property: A property P is called a trivial property if P is ∅ or P = L, where L is a Turing recognizable language.

In more formal terms, let P be a language consisting of Turing machine descriptions where P fulfills two conditions.

1.    First, P is nontrivial—it contains some, but not all, TM descriptions.

2. Second, P is a property of the TM’s language—whenever L(M1) = L(M2), we have <M1> ∈ P iff <M2> ∈ P . Here, M1 and M2 are any TMs. Prove that P is an undecidable language.

Here are a few more decision problems that Rice’s theorem implies are undecidable. This list is certainly not exhaustive.

·        (Assuming L is a recursively enumerable language):  AcceptsL: Given a TM T , is L(T ) = L?

·        Accepts Something: Given a TM T , is there at least one string in L(T )?

·        Accepts Two Or More: Given a TM T , does L(T ) have at least two elements?

·        Accepts Finite: Given a TM T , is L(T ) finite?

·        Accepts Recursive: Given a TM T , is L(T ) (which by definition is recursively enumerable) recursive?

 Also, Study about: 

• Mealy Machine
• Moore Machine
• Rice Theorem
• Brief about Turing Machine
• Multi Dimension Turing Machine
• Multiple Turing Machine
• Parikh Theorem in TOC
• Parse Tree or Derivation Tree
• What do you Understand by Derivation
• MyHill Nerode Theorem
• Minimize Myhill Nerode Theorem
• Push Down Automata
• Know Where we use Automata
• What do you understand by Derivation of Grammar
• What is Context-free Grammar
• Example based on CFG
• Regular Expression in TOC

Also Read, some interview tips

• Why Should I Hire You?
• What are your weaknesses?
• What are your greatest strengths?
• Tell me about yourself.
• What's the reason behind leaving your current position at your company?
• Do You Know how the power of Keywords impacts on Resume?
• Top 8 Proofreading Tips and Techniques in 2022.
• Top Ten Technical Resume Writing Tips in 2022.
• Tips for your resume before you get entry to Job Market
• What Questions you can ask HR during the Interview.
• How to make an impressive resume?
• Best Resume writing Technique.
• What Questions you can ask HR during the Interview.