Satz von Rice

Einfache Sprache

Def. Satz von Rice

Für jede Nicht-triviale semantische Eigenschaft $L$ von Turingsmaschinen ist das Halteproblem für Turingmaschinen Turing-reduzierbar auf $L$. Also

$$\mathrm{HALT_TM}\leq_T L\;.$$

Beweis: Sei $L$ eine sematische Eigenschaft