Turingreduktion
Einfache Sprache
Def. Turingreduktion
Ein Sprache $L$ ist Turing-reduzierbar zu einer Sprache $L'$, geschrieben $L\leq_T L'$, wenn eine Orakel-Turingmaschine $\mathcal M^{L'}$ existiert, die $L$ entscheidet.
Einfache Sprache
Def. Turingreduktion
Ein Sprache $L$ ist Turing-reduzierbar zu einer Sprache $L'$, geschrieben $L\leq_T L'$, wenn eine Orakel-Turingmaschine $\mathcal M^{L'}$ existiert, die $L$ entscheidet.