1 Rice’s Theorem 1.1 Properties
Checking Properties
Given M
Does L(M) contain ⟨M⟩? Is L(M) non-empty?
Is L(M) empty?
Is L(M) infinite?
Is L(M) finite?
Is L(M) co-finite (i.e., is L(M) finite)? Is L(M) = Σ∗?
None of these properties can be decided. This is the content of Rice’s Theorem.
Properties
Definition 1. A property of languages is simply a set of languages. We say L satisfies the property
P if L ∈ P.
Definition 2. For any property P, define language LP to consist of Turing Machines which accept
Undecidable
Undecidable
a language in P:
Deciding LP: deciding if a language represented as a TM satisfies the property P.
• Example: {⟨M⟩ | L(M) is infinite}; Etm = {⟨M⟩ | L(M) = ∅}
• Non-example: {⟨M ⟩ | M has 15 states} ←− This is a property of TMs, and not languages!
Trivial Properties
Definition 3. A property is trivial if either it is not satisfied by any r.e. language, or if it is
satisfied by all r.e. languages. Otherwise it is non-trivial. Example 4. Some trivial properties:
• Pall = set of all languages
• Pr.e. = set of all r.e. languages
• P where P is trivial
• P = {L | L is recognized by a TM with an even number of states} = Pr.e.
Observation. For any trivial property P, LP is decidable. (Why?) Then LP = Σ∗ or LP = ∅.
1
LP ={⟨M⟩|L(M)∈P}
1.2 Main Theorem
Rice’s Theorem
Proposition 5. If P is a non-trivial property, then LP is undecidable.
• Thus {⟨M ⟩ | L(M ) ∈ P} is not decidable (unless P is trivial)
We cannot algorithmically determine any interesting property of languages represented as Tur- ing Machines!
Properties of TMs
Note. Properties of TMs, as opposed to those of languages they accept, may or may not be decidable.
Example 6.
{⟨M⟩ | M has 193 states}
{⟨M ⟩ | M uses at most 32 tape cells on blank input} {⟨M ⟩ | M halts on blank input} {⟨M ⟩ | on input 0011 M at some point writes the
Decidable Undecidable
symbol $ on its tape} Proof of Rice’s Theorem
Rice’s Theorem
If P is a non-trivial property, then LP is undecidable.
Proof. Suppose P non-trivial and ∅ ̸∈ P. If ∅ ∈ P, then in the following we will be showing LP is undecidable. Then LP = LP is also undecidable.
Recall LP = {⟨M⟩|L(M) satisfies P}. We’ll reduce Atm to LP. Then, since Atm is undecidable, LP is also undecidable. Broadly the idea behind the reduction is as follows. Since P is non-trivial, at least one r.e. language satisfies P. i.e., L(M0) ∈ P for some TM M0. We will show a reduction f that maps an instance ⟨M,w⟩ for Atm, to N such that
• If M accepts w then N accepts the same language as M0. Then L(M) = L(M0) ∈ P
• IfM doesnotacceptwthenN accepts∅. ThenL(N)=∅̸∈P
Thus,⟨M,w⟩∈Atm iffN∈LP.
We now describe the reduction precisely. The reduction f maps ⟨M,w⟩ to ⟨N⟩, where N is a
TM that behaves as follows:
On input x
Ignore the input and run M on w
If M does not accept (or doesn’t halt)
then do not accept x (or do not halt) If M does accept w
then run M0 on x and accept x iff M0 does. 2
Notice that indeed if M accepts w then L(N) = L(M0). Otherwise L(N) = ∅. Rice’s Theorem
Recap
Every non-trivial property of r.e. languages is undecidable
• Rice’s theorem says nothing about properties of Turing machines
• Rice’s theorem says nothing about whether a property of languages is recurisvely enumerable or not.
Big Picture . . . again
Languages
Recursively Enumerable
“almost all” properties! Ld, Atm, Etm
Decidable CFL
Atm, Etm, HALT Lanbncn
L0n1n Regular
3