Satz von Rice

Sei die Klasse aller Turing-berechenbaren Funktionen. Sei . Dann ist die Sprache

• Alle Gödelisierungen

nicht berechenbar.

Einfach gesagt

Sei eine nicht-triviale funktionale Eigenschaft von Turing-Maschinen, und sei eine Turing-Maschine. Dann ist das Problem “Besitzt die Eigenschaft ?” nicht entscheidbar.

• Nicht-trivial: Mindestens eine Maschine besitzt diese Eigenschaft nicht
• Funktional: z.B. TM berechnet durch 2 Teilbare Zahl, …