In der Berechenbarkeitstheorie eine Turing-Reduktion (auch bekannt als Cook-Reduktion ) von einem Problem A zu einem Problem B ist eine Reduktion, die A löst, vorausgesetzt, die Lösung von B ist bereits bekannt (Rogers 1967, Soare 1987). Es kann als ein Algorithmus verstanden werden, der verwendet werden könnte, um A zu lösen, wenn ihm ein Unterprogramm zum Lösen B zur Verfügung stand. Formal ist eine Turing-Reduktion eine Funktion, die von einer Orakelmaschine mit einem Orakel für B berechnet werden kann. Turing-Reduzierungen können sowohl auf Entscheidungsprobleme als auch auf Funktionsprobleme angewendet werden.
Wenn eine Turing-Reduktion von A bis B vorhanden ist, kann jeder Algorithmus für B verwendet werden, um einen Algorithmus für A zu erzeugen. durch Einfügen des Algorithmus für B an jeder Stelle, an der die Orakelmaschine A das Orakel für B abfragt. Da die Orakelmaschine das Orakel jedoch häufig abfragen kann, benötigt der resultierende Algorithmus möglicherweise asymptotisch mehr Zeit als entweder der Algorithmus für B oder das Orakelmaschinen-Computing A und kann so viel Platz wie beide zusammen beanspruchen.
Die erste formale Definition der relativen Berechenbarkeit, die dann relative Reduzierbarkeit genannt wurde, wurde von Alan Turing 1939 in Bezug auf Orakelmaschinen gegeben. Später, 1943 und 1952, definierte Stephen Kleene ein gleichwertiges Konzept in Bezug auf rekursive Funktionen. 1944 verwendete Emil Post den Begriff "Turing-Reduzierbarkeit", um auf das Konzept zu verweisen.
Eine polynomische Turing-Reduktion wird als Cook-Reduktion nach Stephen Cook bezeichnet.
Definition [ edit ]
Gegeben zwei Sätze von natürlichen Zahlen, wir sagen ist Turing reduzierbar bis und schreiben
wenn es eine Oracle-Maschine gibt, die das berechnet charakteristische Funktion von A bei Betrieb mit Orakel B . In diesem Fall sagen wir auch, A ist B -rekursiv und B -kompatibel .
Wenn es eine Orakelmaschine gibt, die, wenn sie mit einem Orakel betrieben wird B eine Teilfunktion mit der Domäne A berechnet, dann A heißt . 19659031] B -rekursiv nummerierbar und B rechnerisch zahlbar .
Wir sagen A Turing-Äquivalent bis und schreiben Wenn beide und
Gegeben eine Menge Satz wird Turing hard für if für alle . Wenn zusätzlich dann wird Turing complete für .
Beziehung zwischen Turing-Vollständigkeit und rechnerischer Universalität [ edit ]
Die oben definierte Turing-Vollständigkeit entspricht nur teilweise der Vollständigkeit von Turing im Sinne der universalen Computer-Universalität. Insbesondere ist eine Turingmaschine eine universelle Turingmaschine, wenn ihr Halteproblem (d. H. Der Satz von Eingaben, für den sie eventuell angehalten wird) viele eins ist. Daher ist eine notwendige aber unzureichende Bedingung für eine rechnerisch universelle Maschine, dass das Stoppproblem der Maschine für den Satz Turing-vollständig ist. von rekursiv aufzählbaren Mengen.
Beispiel [ edit ]
Es sei angegeben die Menge der Eingabewerte, für die die Turingmaschine mit Index e angehalten wird. Dann die Sätze und
W e "/> 19659139] ] { displaystyle B = {(e, n) mid n in W_ {e} }} sind Turing Äquivalent (hier bezeichnet eine effektive Paarungsfunktion). Eine Reduktion zeigt kann unter Verwendung der Tatsache konstruiert werden dass . Gegeben sei ein Paar ein neuer Index kann unter Verwendung des Satzes von mn so konstruiert sein, dass das Programm ignoriert ihre Eingabe und simuliert lediglich die Berechnung der Maschine mit dem Index e am Eingang n . Insbesondere die Maschine mit dem Index hält entweder bei jedem Eingang an oder bei keinem Eingang. gilt für alle e und n . Da die Funktion i berechenbar ist, zeigt dies . Bei den hier vorgestellten Reduktionen handelt es sich nicht nur um Turing-Reduktionen, sondern um [1] [1: 1] Reduktionen die weiter unten erläutert werden.
sind Turing Äquivalent (hier 
Eigenschaften [ edit ]
Die Verwendung einer Reduktion [ edit ]
Seit jeder Reduktion aus einem Satz B zu einem Satz Ein muss feststellen, ob ein einzelnes Element in A nur in endlich vielen Schritten vorhanden ist, er kann nur endlich viele Fragen der Mitgliedschaft in dem Satz B stellen . Wenn die Menge an Informationen über das Set B zur Berechnung eines einzelnen Bits von A besprochen wird, wird dies durch die Verwendungsfunktion präzisiert. Formal verwenden einer Reduktion die Funktion, die jede natürliche Zahl n an die größte natürliche Zahl m sendet, deren Mitgliedschaft im Satz B . wurde von der Reduzierung abgefragt, als die Mitgliedschaft von n in A bestimmt wurde.
Stärkere Reduktionen [ edit ]
Es gibt zwei gängige Wege, Reduktionen zu erzeugen, die stärker sind als die von Turing. Die erste Möglichkeit besteht darin, die Anzahl und Art der Oracle-Abfragen zu begrenzen.
- Ein Satz A ist viele-eins reduzierbar bis B wenn es eine insgesamt berechenbare Funktion für gibt, so dass ein Element n ist in A wenn und nur dann, wenn f ( n ) in B ist. Eine solche Funktion kann verwendet werden, um eine Turing-Reduktion zu erzeugen (durch Berechnen f ( n ), Abfragen des Orakels und Interpretieren des Ergebnisses.
- A A A Tabellenreduzierung oder eine schwache Wahrheitstafelreduzierung muss alle ihre Orakelabfragen gleichzeitig darstellen. Bei einer Reduktion der Wahrheitstabelle gibt die Reduktion auch eine boolesche Funktion (a Wahrheitstabelle ), die bei Beantwortung der Fragen die endgültige Antwort auf die Reduktion liefert. Bei einer Reduktion der schwachen Wahrheitstabelle verwendet die Reduktion die Antworten des Orakels als Grundlage für die weitere Berechnung in Abhängigkeit von den gegebenen Antworten (jedoch nicht unter Verwendung des Orakels). Gleichermaßen ist eine Reduktion der schwachen Wahrheitstabelle eine, für die die Verwendung der Reduktion durch eine berechenbare Funktion begrenzt ist. Aus diesem Grund werden Verringerungen für schwache Wahrheitstabellen manchmal als "beschränkte Turing" -Reduktionen bezeichnet.
Der zweite Weg, um eine stärkere Verminderung der Reduzierbarkeit zu erreichen, besteht darin, die Rechenressourcen zu begrenzen, die das Programm zur Implementierung der Turing-Reduzierung verwenden kann. Diese Grenzen der rechnerischen Komplexität der Reduktion sind wichtig, wenn subrekursive Klassen wie P. untersucht werden. Ein Satz A ist Polynomialzeit zu einem Satz B if es gibt eine Turing-Reduktion von A bis B die in polynomialer Zeit läuft. Das Konzept der Log-Space-Reduktion ist ähnlich.
Diese Reduktionen sind stärker in dem Sinne, dass sie eine feinere Unterscheidung in Äquivalenzklassen ermöglichen und restriktivere Anforderungen erfüllen als Turing-Reduktionen. Folglich sind solche Reduzierungen schwieriger zu finden. Es gibt möglicherweise keine Möglichkeit, eine Reduzierung von mehreren Einheiten von einem Satz auf einen anderen zu erstellen, selbst wenn eine Turing-Reduzierung für dieselben Sätze vorhanden ist.
Schwächere Reduktionen [ edit ]
Nach der Church-Turing-These ist eine Turing-Reduktion die allgemeinste Form einer effektiv kalkulierbaren Reduktion. Dennoch werden auch schwächere Reduktionen berücksichtigt. Ein Satz A wird als arithmetisch in B bezeichnet, wenn A durch eine Formel der Peano-Arithmetik mit B als definiert werden kann ein Parameter. Das Set A ist hyperarithmetisch in B wenn es eine rekursive Ordinalzahl α gibt, so dass A aus der α-iterierte Turing-Sprung von B . Der Begriff der relativen Konstruktivität ist ein wichtiger Begriff der Reduzierbarkeit in der Mengenlehre.
Siehe auch [ edit ]
Referenzen [ edit
- M. Davis, Hrsg., 1965. Das Unentscheidbare - Grundlegende Papiere über unentscheidbare Vorschläge, unlösbare Probleme und berechenbare Funktionen Raven, New York. Reprint, Dover, 2004. ISBN 0-486-43228-9.
- S. C. Kleene, 1952. Einführung in die Metamathematik. Amsterdam: Nordholland.
- S. C. Kleene und E.L. Post, 1954. "Das obere Halbgitter von Stufen rekursiver Unlöslichkeit". Annalen der Mathematik v. 2 n. 59, 379-407.
- Post, E. L. (1944). "Rekursiv zahllose positive Zahlen und Entscheidungsprobleme" (PDF) . Bulletin der American Mathematical Society . 50 : 284–316. doi: 10.1090 / s0002-9904-1944-08111-1 . 2015-12-17
- abgerufen. Turing, 1939. "Logiksysteme auf der Grundlage von Ordnungszahlen." Verfahren der Londoner Mathematics Society ser. 2 v. 45, S. 161–228. Nachgedruckt in "The Undecidable", M. Davis, Hrsg., 1965.
- H. Rogers, 1967. Theorie rekursiver Funktionen und effektive Berechenbarkeit. McGraw-Hill.
- R. Soare, 1987. Rekursiv zahllose Mengen und Grade, Springer
- Davis, Martin (November 2006). "Was ist ... Turing-Reduzierbarkeit?" (PDF) . Bekanntmachungen der American Mathematical Society . 53 (10): 1218–1219 . 2008-01-16 .
Không có nhận xét nào:
Đăng nhận xét