Jump

Einfache Sprache

Def. Jump

Für die Sprache $L$ ist dessen Jump $\mathrm{jump}(L)$ definiert als das Halteproblem für Turingmaschinen für Orakel-Turingmaschine mit dem Orakel $L$.

Bemerke: Wenn $L$ die Leere Sprache ist, dann ist $\mathrm{jump}(L) = \mathrm{HALT_TM}$. Der Jump der leeren Sprache ist das Halteproblem für Turingmaschinen.