Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!
37
Satz von Rice
R bezeichnet also die Menge der TM-berechenbaren Funktionen.
Sei S eine Teilmenge von R mit
. Dann ist die Sprache 
nicht rekursiv.Nicht-triviale Eigenschaften der von einer TM berechneten Funktion sind nicht entscheidbar.
Konsequenzen für die Praxis: Es kann keinen Compiler geben, der entscheidet, ob ein gegebenes TM oder RAM_Programm auf allen Eingaben terminiert, weil der Compiler dazu entscheiden müsste, ob das Programm eine Funktion der Form
berechnet