Rice's Theorem 🍚

We’ve seen in the previous section that there are two main ways to show that a decision problem is undecidable: 1. Using a diagonalization-type argument like we did for the halting problem or 2. Reducing one known undecidable problem to another. Unfortunately diagonalization-type arguments cannot always be made and reductions are sometimes, well, hard 🥲. Is it ever possible to more quickly and more easily show that a problem is undecidable? The answer is a resounding “Rice!”, err, I mean “Yes!”. In this section, we see how Rice’s theorem can be used for just that.

What is Rice's Theorem?

Rice’s theorem was originally discovered and proved by Henry Gordon Rice in 1951. Note that the only (known) connection between the theorem and the indispensable carb is its discoverer’s name. But what does Rice’s theorem say concretely? Details in the following video!

How do we use Rice's theorem to show undecidability?

OK so Rice’s theorem tells us that decision problems about non-trivial properties of languages are undecidable. But what does that mean, really? In the next video, I cover a few different decision problems where I walk you through how to determine whether Rice’s theorem can be used to show that a problem is undecidable.

Exercises

Show/Hide Answer