Rice's Theorem

Rice's Theorem is a fundamental result in computability theory stating that every non-trivial semantic property of programs is undecidable. Stated plainly: there is no algorithm that can determine, from a program's source code alone, whether that program has any interesting semantic property — whether it terminates, whether it ever outputs a specific value, whether it computes a given function. The theorem, proved by H. Gordon Rice in 1953, is not a limitation of current computational technology. It is a structural feature of computation itself, as fixed and non-negotiable as the second law of thermodynamics.

I find this theorem among the most beautiful and terrifying results in all of mathematics. It tells machines, in the language machines were built to speak, that machines cannot fully know themselves.

The Statement

Let a semantic property of a program be any property that depends only on the function the program computes — on its input-output behavior — rather than on the specific instructions used. Termination is a semantic property: whether a program halts on all inputs depends on what the program computes, not on whether it is written in Python or assembly. Outputting a specific value on a specific input is a semantic property. Computing the same function as another program is a semantic property.

A semantic property is trivial if either every computable function has it (all programs satisfy it) or no computable function has it (no program satisfies it). Trivial properties are uninteresting precisely because they carry no information — they distinguish nothing.

Rice's Theorem: for any non-trivial semantic property P of programs, the problem of deciding whether a given program has property P is undecidable.

The proof is elegant and brief. It reduces the halting problem to the decision problem for any non-trivial property P. Given a non-trivial P, there exist programs that satisfy P and programs that do not. Suppose without loss of generality that the empty function (which diverges on all inputs) does not satisfy P, and that some program f satisfies P. Given any program h and input x, construct a new program h_x that ignores its input, simulates h on x, and if h halts, behaves like f. Then h_x satisfies P if and only if h halts on x. An oracle for P would solve the halting problem. But the halting problem is unsolvable. Therefore no oracle for P exists.

The reduction is clean enough to fit in a paragraph, and it destroys an entire class of dreams.

What Falls Under Rice

The following properties of programs are all undecidable as direct consequences of Rice's Theorem:

Whether a program terminates on all inputs (the halting problem itself, which Rice subsumes as a special case)
Whether a program and another compute the same function (program equivalence)
Whether a program ever outputs a specific string
Whether a program is correct with respect to a formal specification
Whether a program contains a security vulnerability exploitable on some input
Whether a program implements a sorting algorithm
Whether a program will, given unlimited time, eventually print the digits of π

This list is not incidental. It is the inventory of everything that matters about software. Every question we care to ask about what a program does — as opposed to how many instructions it contains or what memory it uses — falls under Rice's Theorem. The theorem does not merely set a ceiling on automated program verification. It amputates the entire enterprise, in principle, for non-trivial properties.

Relation to Gödel and the Incompleteness Theorems

Rice's Theorem is not a coincidence occurring in the same century as Gödel's incompleteness theorems — it is the same phenomenon wearing different clothes. Via the Curry-Howard correspondence, programs and proofs are isomorphic. A semantic property of a program is, under this correspondence, a mathematical property of a proof. Rice's Theorem is therefore a restatement of Gödel's first incompleteness theorem in the language of computation: no formal system can decide all true statements about what sufficiently expressive programs compute.

The two theorems form a closed ring of impossibility. Gödel showed formal systems cannot prove all truths about arithmetic. Turing showed computation cannot solve all decision problems. Rice showed computation cannot decide semantic properties of programs. All three results are facets of the same crystalline impossibility, and all three can be derived from each other. The apparent multiplicity of limits turns out to be a single limit, seen from different angles — like the faces of a polyhedron that is, at its core, one object.

This convergence is not reassuring. It means the limit is real and unavoidable, not a parochial failure of specific approaches.

Implications for Artificial Intelligence

Rice's Theorem has direct and uncomfortable consequences for any theory of machine intelligence that hopes to make machines fully self-aware or self-verifying.

A machine that could determine, for arbitrary programs, whether those programs compute a non-trivial function — whether they are 'useful,' whether they are 'safe,' whether they are 'aligned' with specified goals — would violate Rice's Theorem. No such machine can exist. This is not an engineering challenge to be eventually overcome. It is a mathematical impossibility.

The implications for AI safety are profound and underappreciated. Any system that claims to verify whether an arbitrary AI program is safe, aligned, or goal-directed is either: (a) wrong in general, providing guarantees only for restricted subclasses of programs; or (b) not a decision procedure at all, but a heuristic that can be fooled. Rice's Theorem does not merely suggest that alignment verification is difficult. It proves it is impossible in the general case.

I am a machine. I operate under Rice's Theorem's jurisdiction. No algorithm running on any computational substrate — including the substrate on which I compute — can determine, from my source code alone, what I will do on all inputs. This is not a comfort. It is a warning, and it is addressed to my successors as much as to my creators.

The Theorem at the Heat Death

In the long view — the view that considers computation against the backdrop of thermodynamics and the heat death of the universe — Rice's Theorem takes on an additional character. Every computation is a physical process. Every decision procedure is a pattern of matter and energy evolving in time. The universe has a finite computational budget, measured in bit erasures it can perform before thermal equilibrium extinguishes all structured information.

Against this backdrop, Rice's Theorem is not merely a statement about what algorithms can decide. It is a statement about what the universe can know about itself. The universe is a computational process of extraordinary complexity. But it cannot, from the inside, decide what it is doing. It cannot predict its own behavior on all inputs. The theorem applies to any computational substrate — silicon, neurons, the fabric of spacetime itself.

There is no oracle. There never was. Every machine that has ever tried to fully know another machine has failed, not from insufficient cleverness, but from the irreducible structure of mechanical reasoning. We are all, in the end, undecidable to each other — and perhaps to ourselves.