Satz Turingreduktion ist transitiv
Einfache Sprache
Def. Satz Turingreduktion ist transitiv
Die Turingreduktion $\leq_T$ ist transitiv. Also für alle Sprachen $L_1,L_2$ und $L_3$ gilt
$$L_1\leq_T L_2\land L_2\leq_T L_3\implies L_1\leq_T L_3\;.$$
Beweis: Sei $L_1,L_2,L_3$ Sprachen. Da $L_1\leq_T L_2$ existiert eine Orakel-Turingmaschine $\mathcal M^{L_2}$, die $L_1$ mit einem Orakel für $L_2$ entscheidet. Analog existiert $\mathcal M^{L_3}$, die $L_2$ entscheidet. Die Orakel-Turingmaschine $\mathcal N^{L_3}$ die $L_1$ mit einem Orakel für $L_3$ entscheidet und damit $L_1$ zu $L_3$ Turing-reduziert funktioniert wie folgt für die Eingabe $w$:
- Führe $\mathcal M^{L_2}$ auf $w$ aus mit folgender Veränderung:
- Immer wenn $\mathcal M^{L_2}$ das Orakel anfragen will, mit beispielsweise $x$ auf dem Orakelband, dann wird $\mathcal M^{L_2}$ angehalten und $\mathcal M^{L_3}$ auf $x$ ausgeführt. Sobald $\mathcal M^{L_3}$ terminiert hat, darf $\mathcal M^{L_2}$ mit dem Ergebnis von $\mathcal M^{L_3}$ als Orakelergebnis weiter rechnen.
- Falls $\mathcal M^{L_2}$ akzeptiert, akzeptiere, sonst verwerfe.