Lecture Notes: Rice's Theorem - COMP2321

Introduction

• Rice's Theorem: Deals with the decidability of properties of Turing machines.
• Key Question: Can we determine if the language accepted by a Turing machine is regular?

Key Definitions

Definition 24

• Property of Turing Recognisable Languages: A class of languages is called a property if for all languages, the language is Turing recognisable.

Definition 25

• Non-trivial Property: Exists when there are two Turing recognisable languages, ( L_1 ) and ( L_2 ), such that ( L_1 ) has the property and ( L_2 ) does not.
  • If no such languages exist, the property is trivial.

Definition 26

• Language of a Property: Defined for a given property ( P ).

Theorem 32: Rice's Theorem

• Statement: If ( P ) is a non-trivial property, then ( L(P) ) is undecidable.

Proof Outline

1. Non-trivial Property: Assume ( L_1 ) has a property ( P ) and ( L_2 ) does not.
2. Turing Machine ( M ): Suppose ( L(M) = L_1 ).
3. Acceptance Problem: Construct Turing machine ( M' ):
   • Simulates ( M ) on input and behaves as follows:
     1. If ( M ) rejects, ( M' ) rejects.
     2. If ( M ) accepts, ( M' ) simulates another Turing machine ( N ).
4. Behavior of ( M' ):
   • If ( M ) accepts, ( M' ) behaves like ( N ).
   • The language accepted by ( M' ) is the same as ( N ), ( L(N) ).
   • If ( M ) does not accept, ( M' ) accepts no inputs.
5. Contradiction:
   • Suppose ( L(P) ) is decidable.
   • Construct decider ( D ) for ( L(P) ).
   • Using ( D ), construct Turing machine ( M'' ) to decide ATM.
   • ( M'' ) simulates ( D ). If ( D ) accepts, ( M'' ) accepts, if ( D ) rejects, ( M'' ) rejects.
   • Contradiction arises as ATM is not decidable.

Conclusion

• Implication: No decider exists for ( L(P) ) if ( P ) is a non-trivial property, affirming the undecidability of the property.