Rice's Theorem

Imagine a perfect tool. You feed it any program — in any language — and it tells you, with certainty, whether that program ever prints the number 0. Or whether it ever loops forever. Or whether it contains a virus. A universal behavior analyzer that simply reads the source and answers.

Such a tool would be worth a fortune. Antivirus would be flawless, bugs would be caught before shipping, optimizing compilers would be perfect. So why doesn't it exist?

In 1953, a young logician named Henry Gordon Rice proved something far stronger than "it's hard." He proved it is impossible — not just for printing 0, but for every interesting question you could ask about what a program does. This is Rice's theorem, and it is one of the most sweeping limits ever discovered in computer science.

Suppose someone hands you printsZero(P) — a magic analyzer that, for any program $P$, returns YES if $P$ prints 0 and NO if it does not. Below you can play the role of the saboteur. Build a tricky program that uses the analyzer against itself, then run it.

<p class="hint">{{hint}}</p>

<div class="box">
  <div class="label">{{verdict_label}}</div>
  <div class="choices">
    <button id="say-yes" type="button">{{btn_yes}}</button>
    <button id="say-no" type="button" class="ghost">{{btn_no}}</button>
  </div>
</div>

<pre class="code" id="code"></pre>

<button id="run" type="button" class="run" disabled>{{btn_run}}</button>

<div class="status" id="status">{{status_initial}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
code { background: #eef2f6; padding: .05rem .3rem; border-radius: 4px; font-family: ui-monospace, monospace; }
.box { background: #f4f7fa; border: 1px solid #d6e0e8; border-radius: 10px; padding: .7rem .8rem; margin-bottom: .7rem; }
.label { font-size: .85rem; font-weight: 600; color: #1d3557; margin-bottom: .5rem; }
.choices { display: flex; gap: .5rem; flex-wrap: wrap; }
pre.code { background: #1d2733; color: #e7eef5; padding: .8rem 1rem; border-radius: 8px;
           font: 13px/1.5 ui-monospace, monospace; overflow-x: auto; margin: 0 0 .7rem;
           white-space: pre; }
pre.code .kw { color: #7fb3ff; }
pre.code .hl { color: #ffd479; font-weight: 700; }
pre.code .cm { color: #8aa0b2; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0 0; min-height: 1.4em; line-height: 1.4; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
button { font: 600 13px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button.run { background: #0a7d33; border-color: #086628; margin-bottom: .2rem; }
button:disabled { opacity: .45; cursor: not-allowed; }

// Code not found

The trap is always the same. Build a program Trickster that asks the analyzer about itself and then does the opposite: if the analyzer says it prints 0, it stays silent; if it says it does not, it prints 0. Whatever the analyzer answers, Trickster makes it wrong. Since the contradiction works for any claimed analyzer, no correct printsZero can exist — and the same self-referential trick works for any non-trivial property at all.

Rice's theorem is not about speed. It is about possibility — and the verdict is brutal.

• The statement. A semantic property is a property of what a program computes (its input-output behavior), not how its code is written. A property is non-trivial if some programs have it and some don't. Rice's theorem says: every non-trivial semantic property is undecidable. No algorithm can decide it for all programs.
• Status: proven undecidable — Henry Gordon Rice, 1953, in his PhD work. It is a theorem, not a conjecture: settled forever.
• It generalizes the halting problem. "Does this program halt?" is just one non-trivial behavior question. Rice shows the entire family — prints 0, loops forever, computes a square, equals a given program, is virus-free — is equally hopeless.
• The proof is a reduction. Any decider for a non-trivial property could be turned, by self-reference and diagonalization, into a decider for halting. Since halting is undecidable, the property must be too. The demo above is exactly this contradiction in miniature.

The crucial fine print: Rice's theorem bans deciding properties of behavior. Syntactic questions — "does the source contain the word goto?", "is it under 100 lines?" — are perfectly decidable. It is only the meaning of the program, never its text, that lies beyond reach. The same wall stands behind program equivalence.

Rice's theorem is the reason an entire industry is built on approximation rather than certainty:

• Antivirus and malware detection: "is this program malicious?" is a non-trivial behavior property, so no scanner is ever complete. Detection relies on signatures and heuristics, and false positives and negatives are unavoidable.
• Static analysis and linters: tools that hunt for bugs must be sound (never miss) or complete (no false alarms) but provably cannot be both for behavior — so they choose a side and approximate.
• Compiler optimization: deciding "does this code ever have an observable effect?" is undecidable, so compilers use conservative, always-safe rules instead of perfect ones.
• Formal verification: proving "this program meets its spec" can't be fully automatic in general; engineers add annotations, restrict the language, or accept that some programs are unanalyzable.

Understanding Rice's theorem reframes a frustration into a law of nature: when your analyzer says "I can't be sure," it isn't weak — it has hit a boundary no tool can cross. The same lesson echoes through program equivalence and the halting problem.

Rice's theorem delivers a hard, beautiful truth: ask any meaningful question about what a program does — not how it's written — and there can be no algorithm that answers it for every program. The halting problem was the first crack; Rice showed the whole wall is solid.

So the perfect antivirus, the flawless bug-finder, the universal optimizer — they are not merely unbuilt. They are unbuildable, forever. Every tool that inspects behavior must approximate, and that limitation traces straight back to one self-referential trickster, the same one that powers the halting problem. Once you see it, you never look at a "scan complete" message the same way again.