Orakel - Versionsgeschichte

Jana: /* Turing-Reduzierbarkeit */

2018-08-29T15:37:26Z

‎Turing-Reduzierbarkeit

Css am 15. August 2018 um 12:51 Uhr

2018-08-15T12:51:38Z

Css: /* Turing-Reduzierbarkeit */

2018-08-15T12:33:55Z

‎Turing-Reduzierbarkeit

Css am 15. August 2018 um 12:30 Uhr

2018-08-15T12:30:27Z

Css: 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…“

2018-08-15T12:26:00Z

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…“

Neue Seite

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.

@@ Zeile 7: / Zeile 7: @@
 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.
-Beispielsweise lässt sich das Post'sche Korrespondenzproblem $PCP$ wie vorher gezeigt zurückführen auf das Halteproblem $H$, also $T \le_T PCP$. Allgemein sind die meisten Unentscheidbarkeitsbeweise Turing-Reduktionen auf das Halteproblem und verwandte Probleme.
+Beispielsweise lässt sich das Post'sche Korrespondenzproblem $PCP$ wie vorher gezeigt zurückführen auf das Halteproblem $H$, also $H \le_T PCP$. Allgemein sind die meisten Unentscheidbarkeitsbeweise Turing-Reduktionen auf das Halteproblem und verwandte Probleme.
 == Jenseits von Unentscheidbarkeit ==

@@ Zeile 1: / Zeile 1: @@
 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.
+In Registermaschinen kann man zum Beispiel einen Befehl <code>oracle R[i] R[j] ...</code> 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 ==
@@ Zeile 7: / Zeile 7: @@
 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.
-Beispielsweise lässt sich das Post'sche Korrespondenzproblem $PCP$ wie vorher gezeigt zurückführen auf das Halteproblem $H$, also $PCP \le_T H$.
+Beispielsweise lässt sich das Post'sche Korrespondenzproblem $PCP$ wie vorher gezeigt zurückführen auf das Halteproblem $H$, also $T \le_T PCP$. Allgemein sind die meisten Unentscheidbarkeitsbeweise Turing-Reduktionen auf das Halteproblem und verwandte Probleme.

← Nächstältere Version		Version vom 15. August 2018, 12:33 Uhr
Zeile 6:		Zeile 6:

	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.		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.
		+
		+	Beispielsweise lässt sich das Post'sche Korrespondenzproblem $PCP$ wie vorher gezeigt zurückführen auf das Halteproblem $H$, also $PCP \le_T H$.

← Nächstältere Version		Version vom 15. August 2018, 12:30 Uhr
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.