Ein Satz der Berechenbarkeitstheorie, der besagt, dass jede nichttriviale semantische Eigenschaft der von einer Turing-Maschine erkannten Sprache unentscheidbar ist: Es gibt keinen Algorithmus, der für eine beliebige Turing-Maschine entscheidet, ob die von ihr akzeptierte Sprache diese Eigenschaft hat, sofern die Eigenschaft nur von der Sprache abhängt und nicht trivial ist.

Prinzip

Semantische Eigenschaften erkannter Sprachen (Eigenschaften, die nur von der Menge der akzeptierten Wörter abhängen) sind entweder trivial (für alle Maschinen oder für keine wahr) oder unentscheidbar; es gibt kein allgemeines Entscheidungsverfahren für nichttriviale Sprach-Eigenschaften.

Demonstration

Konkretes Beispiel: Die Eigenschaft ‚die von der Maschine erkannte Sprache ist regulär‘ ist eine nichttriviale semantische Eigenschaft und damit nach Rice unentscheidbar: Man kann keinen Algorithmus schreiben, der für eine beliebige Turing-Maschine richtig entscheidet, ob ihre akzeptierte Sprache regulär ist.

Fehlanwendung

Rice auf syntaktische oder Ressourcen-Eigenschaften anzuwenden (z. B. ‚hat die Maschine weniger als 10 Zustände?‘ oder ‚läuft die Maschine in linearer Zeit?‘), die nicht rein semantische Spracheigenschaften sind und entscheidbar sein können; oder zu folgern, Rice mache alle Programmanalysen praktisch unmöglich.

Konsequenz

Erklärt, warum viele nichttriviale Programmeigenschaften (Terminierung für alle Eingaben, Äquivalenz zu einer Spezifikation, nichttriviale Korrektheitseigenschaften) im Allgemeinen unentscheidbar sind, und prägt damit Erwartungen an statische Analysen sowie die Entwicklung von approximativen, konservativen oder domain‑beschränkten Techniken.

Umkehrung

Der umgekehrte Fall ist, dass syntaktische Eigenschaften oder triviale semantische Eigenschaften entscheidbar sind; die Einschränkung auf eine spezielle Klasse von Maschinen oder Sprachen (z. B. endliche Automaten) kann Entscheidbarkeit wiederherstellen.

Abgrenzung

Gilt nur für semantische Eigenschaften von von Turing-Maschinen erkennbaren Sprachen, die nichttrivial und extensional sind (nur vom Sprachinhalt abhängig); schließt syntaktische Merkmale, Ressourcenbegrenzungen, probabilistische Zusicherungen oder eigenschaftsdefinitionen relativ zu eingeschränkten Maschinenklassen aus.

Semantische Spannung

Spannung zwischen semantischer Unentscheidbarkeit (WAS eine Sprache ist) und praktischer Programmanalyse, die sich auf syntaktische Muster, Heuristiken, eingeschränkte Domänen oder konservative Approximationen stützt, um dem allgemeinen unentscheidbaren Fall zu entgehen.

Synthese

Rice formalisiert eine weitreichende Begrenzung: Jede nichttriviale Frage, die nur das von einer Turing-Maschine akzeptierte Wortset betrifft, ist unentscheidbar, sodass Programmanalysen auf Approximationen, Einschränkungen oder nicht‑extensionales Wissen angewiesen sein müssen.