Satz von Rice

Der Satz von Rice ist ein Ergebnis der Theoretischen Informatik. Benannt wurde der Satz nach Henry Gordon Rice, der ihn 1953 veröffentlichte. Er besagt, dass es unmöglich ist, eine beliebige nicht-triviale Eigenschaft der erzeugten Funktion einer Turing-Maschine (oder eines Algorithmus in einem anderen Berechenbarkeitsmodell) algorithmisch zu 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 formalen Sprache gegebenes Verhalten zeigt.

1. ↑ Henry Gordon Rice: Classes of recursively enumerable sets and their decision problems. In: Transactions of the American Mathematical Society. Band 74, 1953, S. 358–366, doi:10.2307/1990888.