Orakel: Unterschied zwischen den Versionen
Css (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „Man ist im Allgemeinen nicht nur daran interessiert, ob und wie gut ein Problem berechenbar ist, sondern auch daran, wie sich Probleme relativ zueinander verha…“) |
Css (Diskussion | Beiträge) |
||
| Zeile 2: | Zeile 2: | ||
In Registermaschinen kann man zum Beispiel einen Befehl <quote>oracle R[i] R[j] ...</quote> einführen. Bei Turingmaschinen würde man ein zusätzliches Band einführen, auf das man dann das Orakel anwenden kann. Wichtig ist jedenfalls, besonders später in der Komplexitätstheorie, dass dieses Orakel keine Zeit braucht. | In Registermaschinen kann man zum Beispiel einen Befehl <quote>oracle R[i] R[j] ...</quote> einführen. Bei Turingmaschinen würde man ein zusätzliches Band einführen, auf das man dann das Orakel anwenden kann. Wichtig ist jedenfalls, besonders später in der Komplexitätstheorie, dass dieses Orakel keine Zeit braucht. | ||
| + | |||
| + | == Turing-Reduzierbarkeit == | ||
| + | |||
| + | Von '''Turing-Reduzierbarkeit''' zwischen zwei Problemen $A$ und $B$, geschrieben $A \le_T B$, redet man, wenn es eine Orakel-Turingmaschine $M$ gibt, mit einem Orakel für $B$, die damit das Problem $A$ lösen kann. | ||
Version vom 15. August 2018, 14:30 Uhr
Man ist im Allgemeinen nicht nur daran interessiert, ob und wie gut ein Problem berechenbar ist, sondern auch daran, wie sich Probleme relativ zueinander verhalten. Hierzu führt man Orakel ein. Ein Orakel ist eine zusätzliche Anweisung einer Maschine, die ein konkretes Problem lösen kann, ohne dafür Zeit zu brauchen.
In Registermaschinen kann man zum Beispiel einen Befehl <quote>oracle R[i] R[j] ...</quote> einführen. Bei Turingmaschinen würde man ein zusätzliches Band einführen, auf das man dann das Orakel anwenden kann. Wichtig ist jedenfalls, besonders später in der Komplexitätstheorie, dass dieses Orakel keine Zeit braucht.
Turing-Reduzierbarkeit
Von Turing-Reduzierbarkeit zwischen zwei Problemen $A$ und $B$, geschrieben $A \le_T B$, redet man, wenn es eine Orakel-Turingmaschine $M$ gibt, mit einem Orakel für $B$, die damit das Problem $A$ lösen kann.
