Satz von Friedberg und Muchnik

Einfache Sprache

Def. Satz von Friedberg und Muchnik

Es existiert eine rekursiv aufzählbare 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}\;.$$