rice theorem states that any non-trivial semantic property of a language which is recognized by a turing machine is undecidable. a property, p, is the language of all turing machines that satisfy that property.

formal definition

if p is a non-trivial property, and the language holding the property, l_p , is recognized by turing machine m, then l_p = {<m> | l(m) ∈ p} is undecidable.

description and properties

• property of languages, p, is simply a set of languages. if any language belongs to p (l ∈ p), it is said that l satisfies the property p.

• a property is called to be trivial if either it is not satisfied by any recursively enumerable languages, or if it is satisfied by all recursively enumerable languages.

• a non-trivial property is satisfied by some recursively enumerable languages and are not satisfied by others. formally speaking, in a non-trivial property, where l ∈ p, both the following properties hold:

  • property 1 − there exists turing machines, m1 and m2 that recognize the same language, i.e. either ( <m1>, <m2> ∈ l ) or ( <m1>,<m2> ∉ l )

  • property 2 − there exists turing machines m1 and m2, where m1 recognizes the language while m2 does not, i.e. <m1> ∈ l and <m2> ∉ l

proof

suppose, a property p is non-trivial and φ ∈ p.

since, p is non-trivial, at least one language satisfies p, i.e., l(m₀) ∈ p , ∋ turing machine m₀.

let, w be an input in a particular instant and n is a turing machine which follows −

on input x

• run m on w
• if m does not accept (or doesn't halt), then do not accept x (or do not halt)
• if m accepts w then run m₀ on x. if m₀ accepts x, then accept x.

a function that maps an instance atm = {<m,w>| m accepts input w} to a n such that

• if m accepts w and n accepts the same language as m₀, then l(m) = l(m₀) ∈ p
• if m does not accept w and n accepts φ, then l(n) = φ ∉ p

since a_tm is undecidable and it can be reduced to lp, lp is also undecidable.