besagt intuitiv, daß es unmöglich ist, einem Algorithmus irgendeine nicht-triviale Eigenschaft der Funktion, die er berechnet, „anzusehen“ (Entscheidbarkeit).

Genauer lautet der Satz von Rice:

Sei ϕ₁, ϕ₂,…eine Aufzählung der berechenbaren Funktionen (welche man durch Arithmeti-sierung aller Turing-Maschinen erhalten kann). Sei C eine beliebige Teilmenge der berechenbaren Funktionen (mit Ausnahme der leeren Menge und der Menge aller berechenbaren Funktionen). Dann ist die Menge {n|ϕ_n ∈ C} unentscheidbar.

Ein Beispiel: Es ist unentscheidbar festzustellen, ob eine gegebene Turing-Maschine eine konstante Funktion berechnet.

Viele unentscheidbare Probleme, wie das Halteproblem oder das Verifikationsproblem, ergeben sich als Spezialfälle des Satzes von Rice.