Question

According to the Rice's Theorem, any non-trivial property of the language recognized by a Turing Machine is:

• A. Decidable
• B. Undecidable
• C. Context-free
• D. Recursive

Hint:

Rice's Theorem only applies to properties of the Language. Properties of the Machine itself (like "Does the TM have 5 states?") are actually decidable.

Answer 1

The Correct Option is B

Concept: Rice's Theorem is a powerful tool used to prove the undecidability of various problems regarding Turing Machines.
• Non-trivial Property: A property that some RE languages have and others do not.
• Property of Language: It concerns what the TM accepts, not how the TM is built.

Step 1: Identifying "Non-trivial".
A property is trivial only if it is true for ALL RE languages or NONE of them. Examples of non-trivial properties: Is $L$ empty? Is $L$ finite? Does $L$ contain '001'?

Step 2: Applying the theorem.
Rice's Theorem states that there is no algorithm (decider) that can take a TM's code. ...and determine if its language has a specific non-trivial property.

Step 3: Conclusion on Undecidability.
Because we cannot write a program to answer these questions for all machines. The property is mathematically categorized as Undecidable.