Satz von Rice

Sei $R$ die Menge aller Turing-berechenbaren Funktionen. Sei $S \subseteq R$ eine nicht-triviale Teilmenge (d.h. $S \neq \emptyset$ und $S \neq R$ ).

Dann ist die Sprache

C (S) := {w \in {0, 1}^{*} ∣ die von M_{w} berechnete Funktion liegt in S}

unentscheidbar.