JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Rice's Theorem: Almost Everything Is Undecidable

The halting problem felled one question. Rice's theorem fells nearly all of them at once: ANY non-trivial property of the language a program computes is undecidable. This guide states it carefully — note the words 'non-trivial' and 'of the language' — shows why the wild claim is true, and marks the line it does not cross.

From one undecidable question to a flood of them

Guides 2 and 3 of this rung handed you a single shocking fact: the halting problem is undecidable — no algorithm can take an arbitrary program and input and always correctly say whether it halts — and the universal acceptance language A_TM ('does machine M accept string w?') is undecidable too, both proved by the diagonalization machine that asks about itself and then does the opposite. That is one question down. You might hope the rest of the questions you care about as a programmer are safe. Rice's theorem crushes that hope in a single sentence: essentially EVERY interesting yes/no question about what a program does is undecidable. Not just halting — emptiness, equivalence, correctness, 'does it ever print 42', all of it.

Before we celebrate or panic, we have to say the theorem CAREFULLY, because two small words do almost all the work and beginners routinely drop one and reach a false conclusion. The two words are 'non-trivial' and, crucially, 'of the language'. Get those wrong and you will either think Rice's theorem is obviously false (it is not) or that it forbids things it cheerfully allows (it does not). So this guide is mostly about reading one sentence slowly. Recall from the decidability rung that the language of a Turing machine M, written L(M), is just the set of strings M accepts. Rice's theorem is about questions whose answer depends only on that set — not on how M is written.

A property of the language, not of the code

Here is the pivotal distinction, and it is the single most misunderstood point in the whole subject. Rice's theorem is about a property of the language a machine recognizes, NOT about every syntactic property of the code. A property P is a yes/no test on Turing machines that is semantic in this exact sense: whenever two machines recognize the SAME language, P gives them the same answer. In symbols, if L(M) = L(N) then P(M) = P(N). The test may only 'see' the set of accepted strings; it must be blind to the machine's internals.

Compare two questions about a machine M. Question A: 'Does L(M) contain the empty string epsilon?' That is semantic — it depends only on which strings M accepts, so any two machines with the same language answer it the same way; Rice's theorem applies, and the question is undecidable. Question B: 'Does the source code of M have exactly 100 states?' That is NOT semantic — two machines can recognize the very same language while one has 100 states and another has 99. Rice's theorem says NOTHING about question B, and indeed B is perfectly decidable: just count the states. Counting states, checking the formatting, asking whether the program contains the letter Q — all decidable, all syntactic, all OUTSIDE Rice's reach. The theorem is a statement about meaning, not about text.

Non-trivial: it must split the recognizable languages in two

The second load-bearing word is non-trivial. A property is trivial when it gives the same answer for ALL Turing machines — either every machine has it, or none does. 'Is L(M) a recognizable language?' is trivial: by definition the language of any Turing machine IS recognizable, so the answer is always yes. 'Does M have a language that both contains and does not contain epsilon?' is trivial the other way: impossible, so always no. Trivial properties are decidable for a silly reason — a decider can ignore its input entirely and print the constant answer. A property is non-trivial when SOME machine has it and SOME machine lacks it; the property genuinely carves the recognizable languages into a non-empty 'yes' pile and a non-empty 'no' pile.

Now we can finally state it cleanly. Rice's theorem: every non-trivial semantic property of the language recognized by a Turing machine is undecidable. Read it as: pick any yes/no test that (1) depends only on L(M) and (2) is not constantly-yes or constantly-no — then no algorithm can decide that test for all machines. 'Is L(M) empty?', 'Is L(M) finite?', 'Is L(M) regular?', 'Does L(M) equal the language of this fixed reference machine?', 'Is L(M) the set of all even-length strings?' — each is semantic, each is non-trivial, so each is undecidable. The theorem does not check them one by one; it forbids them all in a single stroke.

Why it is true: hide the halting problem inside the property

The proof is a reduction — a translator that turns one problem into another — and it reuses the undecidability of A_TM you already proved. The idea is a small piece of cunning: given any non-trivial semantic property P, we build a machine-construction that secretly smuggles the question 'does M accept w?' into the question 'does my constructed machine have property P?'. If we could answer the second, we could answer the first; but the first is known to be undecidable, so the second must be undecidable too. The whole trick rests on being able to build, on demand, a machine whose language is one of exactly two values depending on whether M accepts w.

Set up the construction. Because P is non-trivial, there is at least one language WITH property P and at least one WITHOUT it. The empty language (the machine that accepts nothing) sits on one of those two sides; say, for concreteness, that the empty language does NOT have P (the mirror case is identical). Since P is non-trivial there is some machine T whose language L(T) DOES have P. These two anchors — 'empty has no P, L(T) has P' — are the hinge of the whole argument.

  1. Suppose, for contradiction, that some decider D answers the property: D(machine) = yes exactly when that machine's language has P. We will use D to decide A_TM ('does M accept w?'), which is impossible — that contradiction is the goal.
  2. Given an arbitrary M and w, BUILD a new machine M_w that works like this on its own input x: first M_w runs M on w (ignoring x for now); only IF M accepts w does M_w then go on to simulate the anchor machine T on x and accept exactly when T accepts. This building is pure code-rewriting — easy and always halts.
  3. Read off the language of M_w. If M accepts w, then for every x the first stage passes and M_w mimics T, so L(M_w) = L(T) — which HAS property P. If M does NOT accept w, the first stage loops or rejects forever, so M_w accepts nothing: L(M_w) is the empty language — which does NOT have P.
  4. So 'M_w has property P' is TRUE precisely when 'M accepts w' is true. Feed M_w to the supposed decider D: its answer hands us the answer to A_TM. That decides A_TM — contradiction. Therefore no such D exists, and P is undecidable. (Because P is semantic, D really does give M_w the same answer as any other machine with the same language, which is exactly why this works.)

Pause on what just happened, because it is gorgeous. We never looked at WHICH property P was — empty, finite, regular, equal-to-some-fixed-set, anything. We only used that P separates the empty language from some other language. That one foothold was enough to bolt the halting question onto P like a parasite. This is the recurring move of the whole rung: to show a new problem is undecidable, you do not re-run diagonalization from scratch — you REDUCE a known-undecidable problem to it, building a translator that would let a solver of the new problem solve the old impossible one.

What Rice does NOT say — and what it really costs programmers

Now the honest fine print, because Rice's theorem is sweeping but not omnipotent. It does NOT say syntactic questions are undecidable — counting states, checking style, detecting whether the literal string 'goto' appears are all decidable. It does NOT say every instance is hard — for a SPECIFIC fixed program you may well be able to prove what it does; the theorem forbids a SINGLE algorithm that works for ALL programs. It does NOT say the property is unrecognizable — many of these properties are still recognizable (you can confirm a yes), they merely fail to be decidable (you cannot always settle a no). And it does NOT apply to weaker models: properties of the language of a DFA, like emptiness and equivalence, ARE decidable, because a DFA is a finite, fully-mappable object, not a Turing machine. Rice bites only at the top of the Chomsky hierarchy, where full computational power lives.

But where it does bite, it bites hard, and this is the part that should change how you think about software. There is no general halt-checker: no tool can take any program and always correctly decide whether it terminates. There is no general equivalence-checker: 'do these two programs compute the same function?' is undecidable, so no compiler can promise to verify that an optimization preserved behaviour for ALL inputs. There is no perfect bug-finder: 'does this program ever reach this forbidden state?' is undecidable, so fully automatic, complete, sound program verification is mathematically out of reach. Any tool that claims to do these things must be cheating in one of three honest ways: it works only on a restricted language, it sometimes answers 'I don't know', or it is sometimes wrong.