Satz Turingreduktion ist reflexiv
Einfache Sprache
Def. Satz Turingreduktion ist reflexiv
Die Turingreduktion $\leq_T$ ist reflexiv. Also für alle Sprachen $L$ gilt $L\leq_T L$.
Beweis: Sei $L$ eine Sprache und $\mathcal M^L$ eine Orakel-Turingmaschine mit einem Orakel für $L$. Dann existiert eine Turingmaschine $\mathcal M$, die $L$ entscheidet und wie folgt funktioniert für die Eingabe $w$.
- Schreibe $w$ auf das Orakelband.
- Frage das Orakel ab.
- Falls das Orakel sagt das $w$ teil von $L$ ist akzeptiere, sonst verwerfe.