Satz von Kleene und Post

Einfache Sprache

Def. Satz von Kleene und Post

Es existiert eine Sprache $L$ so, dass die Leere Sprache einseitig Turing-reduzierbar zu $L$ und $L$ einseitig Turing-reduzierbar auf das Halteproblem für Turingmaschinen ist. Also

$$\varnothing <_T L <_T \text{HALT}_\text{TM}\;.$$