← •   HOME  • UP  •   →
Top/Reduction/Rice's theorem  

6.5. Rice's Theorem

On this page, we find an infinite collection of uncomputable languages.


Nontrivial problems

Say that a language S is trivial if either S = ∅ or S = ∅.

Any trivial problem is computable. For ∅, a program just always answers no. For ∅, always answer yes.


Equivalence of programs

Say that two programs p and q are equivalent (written p ≅ q) if, for every x, φp(x) = φq(x), even in the case where the answer is ⊥. Two equivalent programs do the same as each other on the same input.


Respecting equivalence

Now let's turn to languages (as computational problems).

Definition. Language S respects equivalence if, whenever p and q are equivalent programs, either p and q are both in S or p and q are both not in S.

So a language that respects equivalence cannot distinguish equivalent programs from on another. If p ≅ q then S cannot contain p but not q.


Rice's theorem

Theorem (Rice's Theorem) If S is a nontrivial language that respects equivalence, then S is uncomputable.

Proof. Suppose that S is a nontrivial language that respects equivalence.

Write a program LOOP that loops forever on all inputs. We can assume that LOOP is not in S. (If LOOP is in S, then look at S instead. S is computable if and only if S is computable.)

Since S is nontrivial, it is not empty, and we can select a program Y that is in S. To summarize, we have programs Y and LOOP where

Y ∈ S,
LOOP ∉ S.

To show that S is uncomputable, it suffices to reduce HALT to S. The reduction R(p, x) looks similar to previous reductions that we have done. Define R(p, x) = qp, x where qp, x is as follows. 

  qp, x(z)
  1. Run p on input x.
  2. Run Y on input z, and give 
     the same answer that it gives.

For R(p, x) to be a mapping reduction from HALT to S, it must be the case that

(p, x) ∈ HALT ⇔ R(p, x) ∈ S.

Let's start by proving the ⇒ part of that. Notice that

(p, x) ∈ HALT ⇒ φp(x)↓
  ⇒ qp, x ≅ Y
(since qp, x gets to line 2 for every z,
and at line 2 it behaves exactly like Y).
  ⇒ qp, x ∈ S
(since Y ∈ S and S respects equivalence)
  ⇒ R(p, x) ∈ S
(since R(p, x) is defined to be qp, x)

That is half of what we need to show. Now we just need to show that R(p, x) ∈ S ⇒ (p, x) ∈ HALT.

R(p, x) ∈ S ⇒ qp, x ∈ S
(since R(p, x) is defined to be qp, x)
  ⇒ qp, x is not equivalent to LOOP
(since S respects equivalence
and LOOP ∉ S)
  ⇒ φp(x)↓
(by inspection of the definition of qp, x.
If φp(x)↑, then qp, x gets stuck in line 1,
and it is equivalent to LOOP.)
  ⇒ (p, x) ∈ HALT
◊

Some consequences of Rice's theorem

Rice's theorem implies that each of the following languages is uncomputable. We write L(p) for the set of all strings s such that φp(s) = yes.

  1. L1 = {p | L(p) = ∅}
  2. L2 = {p | L(p) is a regular language}
  3. L3 = {p } L(p) contains all strings}
  4. L3 = {p | φp(x)↓ for all x}
  5. L4 = {p | φp(x) ↓ when x is an even length string and φp(x)↑ when x is an odd length string}

It should be clear that each of those languages is nontrivial. Let's show that language L1 respects equivalence. Suppose that p and q are two equivalent programs.

p ∈ L1 ⇒ L(p) = ∅
  ⇒ p does not accept any inputs
  ⇒ q does not accept any inputs
(since q ≅ p)
  ⇒ L(q) = ∅
  ⇒ q ∈ L1

(To show that S respects equivalence, it suffices to show that, for any two equivalent programs p and q,

p ∈ S ⇒ q ∈ S

The other direction,

q ∈ S ⇒ p ∈ S

follows immediately by simply switching p and q.)


A common mistake

It is common for students to confuse language L3 above, defined by

L3 = {p | L(p) contains all strings}

with the set that contains all strings, which is trivial and so is computable. But the two are very different. To illustrate the difference, here is a program Q. Is Q in L3? The interesting inputs of Q are positive integers, so assume that n is a positive integer. 

  Q(n)
  k = n
  while k ≠ 1 do
   if k is even
     k = k/2
   else
     k = 3*k + 1
   end if
  end while

  answer yes

Does Q answer yes on every positive integer n? It is not so obvious. In fact, nobody knows whether Q answers yes on every positive integer n.

 

← •   HOME  • UP  •   →
Top/Reduction/Rice's theorem