Einseitige Turingreduktion

Einfache Sprache

Def. Einseitige Turingreduktion

Falls nur eine die Turingreduktion nur von links nach rechts gilt schreiben wir $<_T$ und nennen sie einseitig reduzierbar.