imported>Reinhard Kraasch am 2. Dezember 2025 um 15:50 Uhr

2025-12-02T15:50:53Z

Neue Seite

Der '''Satz von Rice''' ist ein Ergebnis der [[Theoretische Informatik|Theoretischen Informatik]]. Benannt wurde der Satz nach [[Henry Gordon Rice]], der ihn 1953 veröffentlichte.<ref>{{Literatur|Autor=Henry Gordon Rice|Titel=Classes of recursively enumerable sets and their decision problems|Sammelwerk = Transactions of the American Mathematical Society|Band = 74|Jahr = 1953|Seiten=358-366|DOI=10.2307/1990888}}</ref>
Er besagt, dass es unmöglich ist, eine beliebige [[Trivialität#Komplexität (Theoretische Informatik)|nicht-triviale Eigenschaft]] der erzeugten Funktion einer [[Turing-Maschine]] (oder eines [[Algorithmus]] in einem anderen [[Berechenbarkeit]]smodell) algorithmisch zu [[Entscheidbarkeit|entscheiden]].

Für spezielle Klassen von Algorithmen ist es zwar möglich, – auch automatisiert – einzelne Eigenschaften nachzuweisen,
es gibt jedoch kein allgemeines Verfahren, das für jeden Algorithmus feststellen kann, ob die von ihm beschriebene Funktion ein gewünschtes, in einer üblichen [[formale Sprache|formalen Sprache]] gegebenes Verhalten zeigt.

== Satz ==
Es sei <math>\mathcal P</math> die Menge aller [[Partielle Funktion|partiellen]] [[Berechenbare Funktion|Turing-berechenbaren Funktionen]] und <math>\mathcal S \subsetneq \mathcal P</math> eine nicht-leere, echte Teilmenge davon.
Außerdem sei eine [[Nummerierung (Informatik)|effektive Nummerierung]] vorausgesetzt, die einer [[Natürliche Zahlen|natürlichen Zahl]] <math>n \in \N</math> die dadurch codierte Turing-Maschine <math>M_n</math> zuordnet.

Dann ist die Menge <math>\mathcal C(\mathcal S) = \left\{ n \mid \text{die von }M_n\text{ berechnete Funktion liegt in } \mathcal S \right\}</math> nicht [[Entscheidbarkeit|entscheidbar]].

Nach Konstruktion liegen Indizes äquivalenter Turing-Maschinen entweder alle in <math>\mathcal C( \mathcal S)</math> oder alle im [[Komplement (Mengenlehre)|Komplement]].
Man sagt auch, dass <math>\mathcal S</math> eine [[Semantik| semantische]] Eigenschaft von Turing-Maschinen beschreibt, entsprechend heißt <math>\mathcal C ( \mathcal S)</math> eine [[semantische Menge]].

== Anwendungen ==

Aus dem Satz von Rice folgt beispielsweise, dass es keinen Algorithmus gibt, der für jede Turing-Maschine entscheidet, ob sie für jede Eingabe hält oder nicht. <math>\mathcal S = \mathcal R</math> ist hierbei die Menge aller [[Totale Funktion|total]] berechenbaren Funktionen.

Ebenso ist es nicht entscheidbar, ob eine Turing-Maschine eine vorgegebene Funktion <math>f \in \mathcal P</math> berechnet. <math>\mathcal S = \{f\}</math> enthält dann nur diese eine Funktion.
Daraus folgt, dass erst recht das Problem der [[Programmäquivalenz]] nicht entscheidbar ist.

Auch lässt sich nicht entscheiden, ob die berechnete Funktion etwa [[Injektivität|injektiv]], [[Surjektivität|surjektiv]], [[Monotone Abbildung|monoton]] oder [[Konstante Funktion|konstant]] ist.

== Beweisidee ==

Der Beweis ist eine [[Reduktion (Theoretische Informatik)|Many-One-Reduktion]] des speziellen [[Halteproblem]]s <math>K</math> auf <math>\mathcal C(\mathcal S)</math> für ein beliebiges nicht-triviales <math>\mathcal S</math>.
Er wird hier durch [[Pseudocode]] skizziert.

Es sei <math>\emptyset \neq \mathcal S \subsetneq \mathcal P</math> nicht-trivial.
Wir können ohne Einschränkung annehmen, dass die überall undefinierte Funktion <math>\bot</math> nicht in <math>\mathcal S</math> liegt, sonst gehe man zum Komplement über.
Sei weiter <math>f \in \mathcal S</math> eine beliebige, fest gewählte Funktion (hier geht ein, dass <math>\mathcal S</math> nicht-trivial ist), die durch die Turing-Maschine <math>M_f</math> berechnet werde.

Man betrachte für eine beliebige Turing-Maschine <math>M_n</math> den folgenden Algorithmus:

:Funktion <math>N_n(x)</math>:
::simuliere <math>M_n</math> mit Eingabe <math>n</math>
::simuliere anschließend <math>M_f</math> mit Eingabe <math>x</math>
::Ausgabe

Er hat folgende Eigenschaften:
*Die [[Gödelnummer]] von <math>N_n</math> ist aus <math>n</math> berechenbar. Dies geschehe durch die Funktion <math>g \in \mathcal P</math>, d. h. <math>\forall x:n \in \N \colon M_{g(n)}(x) = N_n(x)</math>
*Falls <math>M_n</math> auf der Eingabe <math>n</math> terminiert, berechnet <math>N_n</math> dieselbe Funktion wie <math>M_f</math>, also gerade <math>f</math> und damit eine Funktion aus <math>\mathcal S</math>.
*Andernfalls berechnet <math>N_n</math> die überall undefinierte Funktion <math>\bot</math>, also gemäß obiger Annahme eine Funktion aus dem Komplement von <math>\mathcal S</math>.
*Nach Voraussetzung liegt also die von <math>N_n</math> berechnete Funktion genau dann in <math>\mathcal S</math>, wenn die Berechnung von <math>M_n(n)</math> terminiert.

Wäre nun <math>\mathcal C (\mathcal S)</math> durch eine Turing-Maschine <math>M</math> entscheidbar, so würde man durch Davorschalten eines Algorithmus für <math>g</math> schließlich zu einem Algorithmus zur Lösung des speziellen Halteproblems gelangen, genauer hätte man für jede natürliche Zahl <math>n</math>, dass <math>M_n</math> hält auf <math>n</math> genau dann wenn <math>M</math> auf <math>g(n)</math> die Ausgabe 1 hat, das heißt feststellt, dass <math>g(n)</math> in <math>\mathcal C (\mathcal S)</math> liegt.
Da dies nicht möglich ist, kann <math>\mathcal C (\mathcal S)</math> nicht entscheidbar sein.

== Analogon für rekursiv aufzählbare Eigenschaften ==
Auf eine analoge Weise lassen sich die [[rekursiv aufzählbar]]en (r. a.) semantischen Eigenschaften von Turing-Maschinen
charakterisieren.<ref>Rogers 1967, 324</ref> Sei <math>\mathcal S \subseteq \mathcal P(\N)</math> ein [[Mengensystem|System]] von r. a. Mengen.
Dann ist die [[Indexmenge (Berechenbarkeitstheorie)|Indexmenge]]
:<math>\mathcal C(\mathcal S) = \left\{ n \mid \text{die von }M_n\text{ erkannte Menge liegt in }\mathcal S \right\}</math>
genau dann selbst r. a., wenn es eine r. a. Menge <math>\mathcal{D}</math> von [[Gödelnummer]]n
endlicher Mengen mit folgender Eigenschaft gibt:
:<math>\forall A \subseteq \N \colon A \in S \Leftrightarrow (A \text{ rekursiv aufzählbar}\ \land\ \exists D \subseteq_{\text{fin}} \N \colon (\#D \in \mathcal{D} \wedge D \subseteq A))</math>
Das heißt, <math>\mathcal S</math> enthält genau die rekursiv aufzählbaren Mengen, die eine endliche Teilmenge <math>D</math> haben, deren Gödelnummer <math>\#D</math> in <math>\mathcal{D}</math> liegt.

Dass eine solche Menge <math>\mathcal C(\mathcal S)</math> rekursiv aufzählbar ist, ist leicht einzusehen. Man startet dazu nacheinander die Berechnungen aller Turingmaschinen und gleichzeitig eine Aufzählung von <math>\mathcal{D}</math>. Immer wenn es eine Turing-Maschine <math>M_n</math> gibt, die bereits alle Elemente einer schon aufgezählten endlichen Menge <math>D</math> ausgegeben hat, gibt man <math>n</math> aus. Dass alle anderen Mengen nicht rekursiv aufzählbar sein können, lässt sich ähnlich dem Satz von Rice durch die Unlösbarkeit des Halteproblems zeigen.

== Literatur ==
*{{Literatur | Autor= [[Hartley Rogers]]| Titel= Theory of recursive functions and effective computability| Verlag= McGraw-Hill| Jahr=1967 }}

== Einzelnachweise ==
<references />

[[Kategorie:Berechenbarkeitstheorie]]

Satz von Rice - Versionsgeschichte

imported>Reinhard Kraasch am 2. Dezember 2025 um 15:50 Uhr