Berechenbarkeitstheorie, auch genannt recursion Theorie, ist ein Zweig der mathematischen Logik und Informatik, die in den 1930er Jahren mit der Studie von berechenbaren Funktionen und Graden von Turing entstanden ist. Das Feld ist seitdem gewachsen, um die Studie der verallgemeinerten Berechenbarkeit und definability einzuschließen. In diesen Gebieten, recursion Theorie überlappt mit der Probetheorie und wirksamen beschreibenden Mengenlehre.

Die grundlegenden durch die recursion Theorie gerichteten Fragen sind "Was bedeutet es für eine Funktion von den natürlichen Zahlen bis sich, berechenbar zu sein?" und "Wie können nichtberechenbare Funktionen in eine auf ihrem Niveau der Nichtberechenbarkeit gestützte Hierarchie eingeteilt werden?". Die Antworten auf diese Fragen haben zu einer reichen Theorie geführt, die noch aktiv erforscht wird.

Theoretiker von Recursion in der mathematischen Logik studieren häufig die Theorie der Verhältnisberechenbarkeit, reducibility Begriffe und in diesem Artikel beschriebene Grad-Strukturen. Das hebt sich von der Theorie von subrekursiven Hierarchien, formellen Methoden und formellen Sprachen ab, der in der Studie der Berechenbarkeitstheorie in der Informatik üblich ist. Es gibt beträchtliches Übergreifen in Kenntnissen und Methoden zwischen diesen zwei Forschungsgemeinschaften jedoch, und keine feste Linie kann zwischen ihnen gezogen werden.

Berechenbare und unberechenbare Sätze

Theorie von Recursion ist in den 1930er Jahren, mit der Arbeit von Kurt Gödel, Kirche von Alonzo, Alan Turing, Stephen Kleene und Emil Post entstanden.

Die grundsätzlichen Ergebnisse, die die Forscher erhalten haben, haben Berechenbarkeit von Turing als die richtige Formalisierung der informellen Idee von der wirksamen Berechnung gegründet.

Diese Ergebnisse haben Stephen Kleene (1952) dazu gebracht, die zwei Namen "die These der Kirche" (Kleene 1952:300) und "die These von Turing" ins Leben zu rufen (p. 376). Heutzutage werden diese häufig als eine einzelne Hypothese, die Kirch-Turing-These betrachtet, die feststellt, dass jede Funktion, die durch einen Algorithmus berechenbar ist, eine berechenbare Funktion ist. Obwohl am Anfang skeptisch, vor 1946 hat Gödel für diese These gestritten:

: "Tarski hat in seinem Vortrag betont (und ich denke zurecht) die große Wichtigkeit vom Konzept der allgemeinen Rekursivkeit (oder die Berechenbarkeit von Turing). Es scheint mir, dass diese Wichtigkeit größtenteils darin besteht auf Grund dessen, dass mit diesem Konzept man zum ersten Mal geschafft hat, einen absoluten Begriff einem interessanten erkenntnistheoretischen Begriff, d. h., ein nicht abhängig vom Formalismus chosen. *" (Gödel 1946 in Davis 1965:84) zu geben.

Mit einer Definition der wirksamen Berechnung ist die ersten Beweise gekommen, dass es Probleme in der Mathematik gibt, die nicht effektiv entschieden werden kann. Kirche (1936a, 1936b) und Turing (1936), begeistert durch Techniken, die von Gödel (1931) verwendet sind, um seine Unvollständigkeitslehrsätze zu beweisen, hat unabhängig demonstriert, dass Entscheidungsproblem nicht effektiv entscheidbar ist. Dieses Ergebnis hat gezeigt, dass es kein algorithmisches Verfahren gibt, das richtig entscheiden kann, ob willkürliche mathematische Vorschläge wahr oder falsch sind.

gezeigt hat, sind viele Probleme der Mathematik unentscheidbar gewesen, nachdem diese anfänglichen Beispiele gegründet wurden. 1947 haben Markov und Posten unabhängige Papiere veröffentlicht zeigend, dass das Wortproblem für Halbgruppen nicht effektiv entschieden werden kann. Dieses Ergebnis erweiternd, haben Pyotr Novikov und William Boone unabhängig in den 1950er Jahren gezeigt, dass das Wortproblem für Gruppen nicht effektiv lösbar ist: Es gibt kein wirksames Verfahren, das, in Anbetracht eines Wortes in einer begrenzt präsentierten Gruppe, entscheiden wird, ob das durch das Wort vertretene Element das Identitätselement der Gruppe ist. 1970 hat Yuri Matiyasevich (das Verwenden von Ergebnissen von Julia Robinson) den Lehrsatz von Matiyasevich bewiesen, der andeutet, dass das zehnte Problem von Hilbert keine wirksame Lösung hat; dieses Problem hat gefragt, ob es ein wirksames Verfahren gibt, um zu entscheiden, ob eine Gleichung von Diophantine über die ganzen Zahlen eine Lösung in den ganzen Zahlen hat. Die Liste von unentscheidbaren Problemen führt zusätzliche Beispiele von Problemen ohne berechenbare Lösung an.

Dessen Studie mathematische Aufbauten effektiv durchgeführt werden können, wird manchmal rekursive Mathematik genannt; das Handbuch der Rekursiven Mathematik (Ershov u. a. 1998) bedeckt viele der bekannten läuft auf dieses Feld hinaus.

Berechenbarkeit von Turing

Die Hauptform der in der recursion Theorie studierten Berechenbarkeit wurde von Turing (1936) eingeführt. Wie man sagt, ist eine Reihe von natürlichen Zahlen ein berechenbarer Satz (auch hat einen entscheidbaren, rekursives, oder Turing berechenbarer Satz genannt), wenn es eine Maschine von Turing gibt, die, in Anbetracht einer Nummer n, mit der Produktion 1 hinkt, wenn n im Satz und den Halten mit der Produktion 0 ist, wenn n nicht im Satz ist. Eine Funktion f von den natürlichen Zahlen bis sich ist eine rekursive oder (Turing) berechenbare Funktion, wenn es eine Maschine von Turing dass, auf dem Eingang n, den Halten und der Rückproduktion f (n) gibt. Der Gebrauch von Maschinen von Turing hier ist nicht notwendig; es gibt viele andere Modelle der Berechnung, die dieselbe Rechenmacht wie Maschinen von Turing haben; zum Beispiel haben die μ-Recursive-Funktionen von primitivem recursion und dem μ Maschinenbediener vorgeherrscht.

Die Fachsprache für rekursive Funktionen und Sätze wird nicht völlig standardisiert.

Die Definition in Bezug auf μ-Recursive-Funktionen sowie eine verschiedene Definition von Rekursiv-Funktionen durch Gödel hat zum traditionellen Namen geführt, der für Sätze und durch eine Maschine von Turing berechenbare Funktionen rekursiv ist. Entscheidbare Stämme des Wortes vom deutschen Wort Entscheidungsproblem, der in den ursprünglichen Zeitungen von Turing und anderen verwendet wurde. Im zeitgenössischen Gebrauch hat der Begriff "berechenbare Funktion" verschiedene Definitionen: Gemäß Cutland (1980) ist es eine teilweise rekursive Funktion (der für einige Eingänge unbestimmt sein kann), während gemäß Soare (1987) es eine Summe rekursiv (gleichwertig, allgemein rekursiv) Funktion ist. Dieser Artikel folgt der zweiten von dieser Vereinbarung. Soare (1996) gibt zusätzliche Anmerkungen über die Fachsprache.

Nicht jeder Satz von natürlichen Zahlen ist berechenbar. Das stockende Problem, das der Satz (Beschreibungen) Maschinen von Turing ist, die auf dem Eingang 0 hinken, ist ein weithin bekanntes Beispiel eines nichtberechenbaren Satzes. Die Existenz von vielen nichtberechenbaren Sätzen folgt aus den Tatsachen, dass es nur zählbar viele Maschinen von Turing, und so nur zählbar viele berechenbare Sätze gibt, aber es gibt unzählbar viele Sätze von natürlichen Zahlen.

Obwohl das Stockende Problem nicht berechenbar ist, ist es möglich, Programm-Ausführung vorzutäuschen und eine unendliche Liste der Programme zu erzeugen, die wirklich hinken. So ist das stockende Problem ein Beispiel rekursiv enumerable Satz, der ein Satz ist, der durch eine Maschine von Turing aufgezählt werden kann (andere Begriffe für rekursiv enumerable schließen berechenbar enumerable und halbentscheidbar ein). Gleichwertig ist ein Satz rekursiv enumerable, wenn, und nur wenn es die Reihe von etwas berechenbarer Funktion ist. Rekursiv enumerable Sätze, obwohl nicht entscheidbar im Allgemeinen, sind im Detail in der recursion Theorie studiert worden.

Gebiete der Forschung

Mit der Theorie von rekursiven Sätzen und Funktionen beginnend, die oben beschrieben sind, ist das Feld der recursion Theorie gewachsen, um die Studie von vielen nah zusammenhängenden Themen einzuschließen. Das sind ziemlich abhängige Gebiete der Forschung: Jedes dieser Gebiete zieht Ideen und ergibt sich aus anderen, und die meisten recursion Theoretiker sind mit der Mehrheit von ihnen vertraut.

Verhältnisberechenbarkeit und die Grade von Turing

Die Theorie von Recursion in der mathematischen Logik hat sich auf Verhältnisberechenbarkeit, eine Generalisation der definierten Berechenbarkeit von Turing mit dem Orakel Maschinen von Turing traditionell konzentriert, die von Turing (1939) eingeführt sind. Eine Orakel-Maschine von Turing ist ein hypothetisches Gerät, das, zusätzlich zum Durchführen der Handlungen einer regelmäßigen Maschine von Turing, im Stande ist, Fragen eines Orakels zu stellen, das ein besonderer Satz von natürlichen Zahlen ist. Die Orakel-Maschine kann nur Fragen der Form stellen "Ist n im Orakel-Satz?". Auf jede Frage wird richtig sofort geantwortet, selbst wenn der Orakel-Satz nicht berechenbar ist. So wird eine Orakel-Maschine mit einem nichtberechenbaren Orakel im Stande sein, Sätze zu schätzen, die ohne ein Orakel nicht berechenbar sind.

Informell ist eine Reihe von natürlichen Zahlen A Turing, der auf einen Satz B reduzierbar ist, wenn es eine Orakel-Maschine gibt, die richtig erzählt, ob Zahlen in, wenn geführt, mit B als der Orakel-Satz sind (in diesem Fall, wie man auch sagt, ist der Satz A von B (relativ) berechenbar und in B) rekursiv. Wenn ein Satz A Turing ist, der auf einen Satz B reduzierbar ist, und B Turing ist, der auf dann reduzierbar ist, wie man sagt, haben die Sätze denselben Grad von Turing (auch genannt Grad der Unlösbarkeit). Der Turing Grad eines Satzes gibt ein genaues Maß dessen, wie unberechenbar der Satz ist.

Die natürlichen Beispiele von Sätzen, die einschließlich vieler verschiedener Sätze nicht berechenbar sind, die Varianten des stockenden Problems verschlüsseln, haben zwei Eigenschaften gemeinsam:

1. Sie sind rekursiv enumerable, und
2. Jeder kann in irgendwelchen anderer über vieleine Verminderung übersetzt werden. D. h. in Anbetracht solcher Sätze A und B gibt es eine berechenbare Gesamtfunktion f solch dass = {x: f (x)  B\. Wie man sagt, sind diese Sätze vieleine Entsprechung (oder M gleichwertig).

Vieleine Verminderungen sind "stärker" als die Verminderungen von Turing: Wenn ein Satz A vielein reduzierbarer auf einen Satz B ist, dann ist A auf B reduzierbarer Turing, aber das gegenteilige hält nicht immer. Obwohl die natürlichen Beispiele von nichtberechenbaren Sätzen der ganze gleichwertige sind, ist es möglich, rekursiv enumerable zu bauen, setzt A und solchen B, dass A Turing ist, der auf B, aber nicht vieleinen reduzierbaren auf B reduzierbar ist. Es kann gezeigt werden, dass jeder rekursiv enumerable Satz vielein reduzierbarer auf das stockende Problem ist, und so das stockende Problem rekursiv enumerable Satz in Bezug auf vieleinen reducibility und in Bezug auf Turing reducibility am meisten kompliziert ist. Posten (1944) hat gefragt, ob jeder rekursiv enumerable Satz entweder berechenbar ist oder Turing, der zum stockenden Problem gleichwertig ist, d. h. ob es nicht rekursiv enumerable Satz mit einem Grad-Zwischenglied von Turing zwischen jenen zwei gibt.

Da Zwischenglied resultiert, hat Posten natürliche Typen rekursiv enumerable Sätze wie das einfache, hypereinfache und Hyperhypersimple-Sätze definiert. Posten hat gezeigt, dass diese Sätze ausschließlich zwischen den berechenbaren Sätzen und dem stockenden Problem in Bezug auf vieleinen reducibility sind. Posten hat auch gezeigt, dass einige von ihnen unter anderen reducibility Begriffen ausschließlich Zwischen-sind, die stärker sind als Turing reducibility. Aber Posten hat offen das Hauptproblem der Existenz rekursiv enumerable Sätze des Zwischengrads von Turing verlassen; dieses Problem ist bekannt als das Problem des Postens geworden. Nach zehn Jahren haben Kleene und Post 1954 gezeigt, dass es Zwischengrade von Turing zwischen denjenigen der berechenbaren Sätze und des stockenden Problems gibt, aber sie haben gescheitert zu zeigen, dass einige dieser Grade rekursiv enumerable Satz enthält. Sehr, kurz nachdem das, Friedberg und Muchnik unabhängig das Problem des Postens durch das Herstellen der Existenz rekursiv enumerable Sätze des Zwischengrads behoben haben. Dieses Groundbreaking-Ergebnis hat eine breite Studie der Grade von Turing rekursiv enumerable Sätze geöffnet, die sich erwiesen haben, eine sehr komplizierte und nichttriviale Struktur zu besitzen.

Es gibt unzählbar viele Sätze, die nicht rekursiv enumerable sind, und die Untersuchung der Grade von Turing aller Sätze so in der recursion Theorie zentral ist wie die Untersuchung rekursiv enumerable Grade von Turing. Viele Grade mit speziellen Eigenschaften wurden gebaut: Hypergeschützt-freie Grade, wo jede hinsichtlich dieses Grads berechenbare Funktion majorized nach einer (unrelativierten) berechenbaren Funktion ist; hohe Grade, hinsichtlich deren eine Funktion f schätzen kann, der jede berechenbare Funktion g im Sinn beherrscht, dass es einen unveränderlichen c je nachdem g solch dass g (x) &lt gibt; f (x) für den ganzen x > c; zufällige Grade, die algorithmisch zufällige Sätze enthalten; 1-allgemeine Grade von 1-allgemeinen Sätzen; und die Grade unter dem stockenden Problem von mit der Grenze rekursiven Sätzen.

Die Studie von willkürlichen (nicht notwendigerweise rekursiv enumerable) Grade von Turing ist mit der Studie des Sprungs von Turing verbunden. In Anbetracht eines Satzes A ist der Sprung von Turing von A eine Reihe von natürlichen Zahlen, die eine Lösung des stockenden Problems für das Orakel Maschinen von Turing verschlüsselt, die mit dem Orakel A laufen. Der Turing Sprung jedes Satzes ist immer des höheren Grads von Turing als der ursprüngliche Satz, und ein Lehrsatz von Friedburg zeigt, dass jeder Satz, der das Stockende Problem schätzt, als der Sprung von Turing eines anderen Satzes erhalten werden kann. Der Lehrsatz des Postens stellt eine nahe Beziehung zwischen der Sprung-Operation von Turing und der arithmetischen Hierarchie her, die eine Klassifikation von bestimmten Teilmengen der natürlichen Zahlen ist, die auf ihrem definability in der Arithmetik gestützt sind.

Viel neue Forschung über Grade von Turing hat sich auf die gesamte Struktur des Satzes von Graden von Turing und des Satzes von Graden von Turing konzentriert, die rekursiv enumerable Sätze enthalten. Ein tiefer Lehrsatz von Shore und Slaman (1999) stellt fest, dass die Funktion, die einen Grad x zum Grad seines Sprungs von Turing kartografisch darstellt, in der teilweisen Ordnung der Grade von Turing definierbar ist. Ein neuer Überblick durch Ambos-Spies und Fejer (2006) gibt eine Übersicht dieser Forschung und seines historischen Fortschritts.

Anderer reducibilities

Ein andauerndes Gebiet der Forschung in der recursion Theorie studiert reducibility Beziehungen außer Turing reducibility. Posten (1944) hat mehrere starke reducibilities, so genannt eingeführt, weil sie Wahrheitstabelle reducibility einbeziehen. Eine Turing Maschine, die einen starken reducibility durchführt, wird eine Gesamtfunktion schätzen, unabhängig von dem Orakel sie damit präsentiert wird. Schwache reducibilities sind diejenigen, wo ein Verminderungsprozess für alle Orakel nicht enden kann; Turing reducibility ist ein Beispiel.

Die starken reducibilities schließen ein:

Ein einer reducibility: A ist ein reduzierbar (oder reduzierbar auf 1) zu B, wenn es eine berechenbare Gesamtinjective-Funktion f solch gibt, dass jeder n in ist, wenn, und nur wenn f (n) in B ist.

Vielein reducibility: Das ist im Wesentlichen ein einer reducibility ohne die Einschränkung das f, injective sein. A ist vielein reduzierbarer (oder M reduzierbar) zu B, wenn es eine berechenbare Gesamtfunktion f solch gibt, dass jeder n in ist, wenn, und nur wenn f (n) in B ist.

Wahrheitstabelle reducibility: A ist auf B reduzierbare Wahrheitstabelle, wenn A Turing ist, der auf B über ein Orakel Maschine von Turing reduzierbar ist, die eine Gesamtfunktion unabhängig vom Orakel schätzt, das es gegeben wird. Wegen der Kompaktheit des Kantor-Raums ist das zum Ausspruch gleichwertig, dass die Verminderung eine einzelne Liste von Fragen präsentiert (nur vom Eingang abhängend) zum Orakel gleichzeitig, und dann gesehen, dass ihre Antworten im Stande sind, eine Produktion zu erzeugen, ohne zusätzliche Fragen unabhängig von der Antwort des Orakels auf die anfänglichen Abfragen zu stellen. Viele Varianten der Wahrheitstabelle reducibility sind auch studiert worden.

Weiter werden reducibilities (positiv, abtrennend, verbindend, geradlinig und ihre schwachen und begrenzten Versionen) im Artikel Reduction (recursion Theorie) besprochen.

Die Hauptforschung über starken reducibilities hat ihre Theorien, beide für die Klasse von allen rekursiv enumerable Sätze sowie für die Klasse aller Teilmengen der natürlichen Zahlen vergleichen sollen. Außerdem, die Beziehungen zwischen dem reducibilities ist studiert worden. Zum Beispiel ist es bekannt, dass jeder Grad von Turing entweder ein Wahrheitstabelle-Grad ist oder die Vereinigung von ungeheuer vielen Wahrheitstabelle-Graden ist.

Reducibilities, die schwächer sind als Turing reducibility (d. h. reducibilities, die durch Turing reducibility einbezogen werden), sind auch studiert worden. Die weithin bekanntsten sind arithmetischer reducibility und hyperarithmetischer reducibility. Diese reducibilities werden mit definability über das Standardmodell der Arithmetik nah verbunden.

Der Lehrsatz von Reis und die arithmetische Hierarchie

Rice hat gezeigt, dass für jede nichttriviale Klasse C (der einige, aber nicht alle R.e.-Sätze enthält) der Index E = {e gesetzt hat: Die eth r.e. gehen unter W ist darin C\hat das Eigentum, dass entweder das stockende Problem oder seine Ergänzung vielein reduzierbarer auf E sind, d. h. kann mit vieleiner Verminderung an E kartografisch dargestellt werden (sieh den Lehrsatz von Rice für mehr Detail). Aber viele dieser Index-Sätze sind noch mehr kompliziert als das stockende Problem. Ähnliche Sätze können mit der arithmetischen Hierarchie klassifiziert werden. Zum Beispiel ist der Index untergegangen die FLOSSE der Klasse aller begrenzten Sätze ist auf dem Niveau Σ, der Index ist untergegangen REC der Klasse aller rekursiven Sätze ist auf dem Niveau Σ, der Index ist untergegangen COFIN aller Cofinite-Sätze ist auch auf dem Niveau Σ und der Index-Satz-SETZER der Klasse aller Turing-ganzen Sätze Σ. Diese Hierarchie-Niveaus werden induktiv definiert, Σ enthält gerade alle Sätze, die rekursiv enumerable hinsichtlich Σ sind; Σ enthält rekursiv enumerable Sätze. Die Index-Sätze gegeben hier sind sogar für ihre Niveaus abgeschlossen, d. h. alle Sätze in diesen Niveaus können auf die gegebenen Index-Sätze reduzierter derjenige sein.

Rückmathematik

Das Programm der Rückmathematik fragt, welche Axiome der Satz-Existenz notwendig sind, um besondere Lehrsätze der Mathematik in Subsystemen der Arithmetik der zweiten Ordnung zu beweisen. Diese Studie wurde von Harvey Friedman begonnen und wurde im Detail von Stephen Simpson und anderen studiert; Simpson (1999) gibt eine ausführliche Diskussion des Programms. Die fraglichen Axiome der Satz-Existenz entsprechen informell zu Axiomen sagend, dass der powerset der natürlichen Zahlen unter verschiedenen reducibility Begriffen geschlossen wird. Das schwächste solches in der Rückmathematik studiertes Axiom ist rekursives Verständnis, das feststellt, dass der powerset des naturals unter Turing reducibility geschlossen wird.

Numberings

Ein Numerieren ist eine Enumeration von Funktionen; es hat zwei Rahmen, e und x und Produktionen der Wert der E-Th-Funktion im Numerieren auf dem Eingang x. Numberings kann teilweise-rekursiv sein, obwohl einige seiner Mitglieder rekursiv, d. h. berechenbare Funktionen ganz sind. Annehmbar oder Gödel numberings sind diejenigen, in die alles andere übersetzt werden können. Ein Friedberg, der (genannt nach seinem Entdecker) numeriert, ist derjenige das ein Numerieren aller teilweise-rekursiven Funktionen; es ist notwendigerweise nicht ein annehmbares Numerieren. Spätere Forschung hat sich auch mit numberings anderer Klassen wie Klassen rekursiv enumerable Sätze befasst. Goncharov hat zum Beispiel eine Klasse rekursiv enumerable Sätze entdeckt, für die die numberings in genau zwei Klassen in Bezug auf den rekursiven Isomorphismus fallen.

Die Vorzugsmethode

:For weitere Erklärung, sieh das Abteilungspostproblem und die Vorzugsmethode im Grad des Artikels Turing.

Das Problem des Postens wurde mit einer Methode genannt die Vorzugsmethode behoben; ein Beweis mit dieser Methode wird ein Vorzugsargument genannt. Diese Methode wird in erster Linie verwendet, um rekursiv enumerable Sätze mit besonderen Eigenschaften zu bauen. Um diese Methode zu verwenden, werden die gewünschten Eigenschaften des zu bauenden Satzes in eine unendliche Liste von Absichten zerbrochen, die als Voraussetzungen bekannt sind, so dass die Zufriedenheit aller Voraussetzungen den Satz veranlassen wird, der gebaut ist, die gewünschten Eigenschaften zu haben. Jede Voraussetzung wird einer natürlichen Zahl zugeteilt, die den Vorrang der Voraussetzung vertritt; so 0 wird dem wichtigsten Vorrang, 1 zum zweitwichtigsten und so weiter zugeteilt. Der Satz wird dann etappenweise, jede Bühne gebaut, die versucht, eine von mehr von den Voraussetzungen entweder durch zu befriedigen, Zahlen zum Satz hinzufügend oder durch Zahlen vom Satz verbietend, so dass der Endsatz die Voraussetzung befriedigen wird. Es kann geschehen, dass Zufriedenheit einer Voraussetzung einen anderen veranlassen wird, unbefriedigt zu werden; die Vorzugsordnung wird verwendet, um zu entscheiden, was man in solch einem Ereignis tut.

Vorzugsargumente sind verwendet worden, um viele Probleme in der recursion Theorie zu beheben, und sind in eine Hierarchie eingeteilt worden, die auf ihrer Kompliziertheit (Soare 1987) gestützt ist. Weil komplizierte Vorzugsargumente technisch und schwierig sein können zu folgen, hat es

traditionell gewesen hat als wünschenswert betrachtet, um Ergebnisse ohne Vorzugsargumente zu beweisen oder zu sehen, ob mit Vorzugsargumenten bewiesene Ergebnisse auch ohne sie bewiesen werden können.

Zum Beispiel hat Kummer eine Zeitung auf einem Beweis für die Existenz von Friedberg numberings veröffentlicht, ohne die Vorzugsmethode zu verwenden.

Das Gitter rekursiv enumerable Sätze

Als Posten den Begriff eines einfachen Satzes als ein R.e.-Satz mit einer unendlichen Ergänzung definiert hat, die nicht jeden unendlichen R.e.-Satz enthält, hat er angefangen, die Struktur rekursiv enumerable Sätze unter der Einschließung zu studieren. Dieses Gitter ist eine gut studierte Struktur geworden. Rekursive Sätze können in dieser Struktur durch das grundlegende Ergebnis definiert werden, dass ein Satz rekursiv ist, wenn, und nur wenn der Satz und seine Ergänzung beide rekursiv enumerable sind. Unendliche R.e.-Sätze haben immer unendliche rekursive Teilmengen; aber andererseits bestehen einfache Sätze, aber haben keine coinfinite rekursive Obermenge. Posten (1944) eingeführt bereits hypereinfach und Hyperhypersimple-Sätze; später wurden maximale Sätze gebaut, die solche R.e.-Sätze sind, dass jede r.e. Obermenge entweder eine begrenzte Variante des gegebenen maximalen Satzes ist oder co-finite ist. Die ursprüngliche Motivation des Postens in der Studie dieses Gitters sollte einen Strukturbegriff solch finden, dass jeder Satz, der dieses Eigentum befriedigt, weder im Grad von Turing der rekursiven Sätze noch im Grad von Turing des stockenden Problems ist. Posten hat solch ein Eigentum nicht gefunden, und die Lösung seines Problems hat Vorzugsmethoden stattdessen angewandt; Harrington und Soare (1991) gefunden schließlich solch ein Eigentum.

Probleme von Automorphism

Eine andere wichtige Frage ist die Existenz von automorphisms in recursion-theoretischen Strukturen. Eine dieser Strukturen ist, dass einer rekursiv enumerable unter der Einschließung modulo begrenzten Unterschied setzt; in dieser Struktur ist A unter B wenn und nur wenn der Satz-Unterschied B − A ist begrenzt. Maximale Sätze (wie definiert, im vorherigen Paragrafen) haben das Eigentum, dass sie automorphic zu nichtmaximalen Sätzen nicht sein können, d. h. wenn es einen automorphism der rekursiven Enumerable-Sätze unter der gerade erwähnten Struktur gibt, dann wird jeder maximale Satz zu einem anderen maximalen Satz kartografisch dargestellt. Soare (1974) hat gezeigt, dass auch das gegenteilige hält, d. h. sind alle zwei maximalen Sätze automorphic. So bilden die maximalen Sätze eine Bahn, d. h. bewahrt jeder automorphism maximality, und irgendwelche zwei maximalen Sätze werden in einander durch einen automorphism umgestaltet. Harrington hat ein weiteres Beispiel eines automorphic Eigentums angeführt: das der kreativen Sätze, die Sätze, die vieleine Entsprechung zum stockenden Problem sind.

Außer dem Gitter rekursiv enumerable Sätze werden automorphisms auch für die Struktur der Grade von Turing aller Sätze sowie für die Struktur der Grade von Turing von R.e.-Sätzen studiert. In beiden Fällen behauptet Küfer, nichttriviale automorphisms gebaut zu haben, die einige Grade zu anderen Graden kartografisch darstellen; dieser Aufbau ist jedoch nicht nachgeprüft worden, und einige Kollegen glauben, dass der Aufbau Fehler und dass die Frage enthält, ob es einen nichttrivialen automorphism der Grade von Turing gibt, ist noch eine der ungelösten Hauptfragen in diesem Gebiet (Slaman und Woodin 1986, Ambos-Spies und Fejer 2006).

Kompliziertheit von Kolmogorov

Das Feld der Kompliziertheit von Kolmogorov und algorithmischen Zufälligkeit wurde während der 1960er Jahre und der 1970er Jahre von Chaitin, Kolmogorov, Levin entwickelt, Martin-Löf und Solomonoff (werden die Namen hier in alphabetischer Reihenfolge gegeben; viel von der Forschung war unabhängig, und die Einheit des Konzepts der Zufälligkeit wurde zurzeit nicht verstanden). Die Hauptidee ist, eine universale Maschine von Turing U zu denken und die Kompliziertheit einer Zahl (oder Schnur) x als die Länge des kürzesten Eingangs p solch dass U (p) Produktionen x zu messen. Diese Annäherung hat frühere Weisen revolutioniert zu bestimmen, wenn eine unendliche Folge (gleichwertig, charakteristische Funktion einer Teilmenge der natürlichen Zahlen) zufällig ist oder nicht durch das Hervorrufen eines Begriffs der Zufälligkeit für begrenzte Gegenstände. Kompliziertheit von Kolmogorov ist nicht nur ein Thema der unabhängigen Studie geworden, aber wird auch auf andere Themen als ein Werkzeug angewandt, um Beweise zu erhalten.

Es gibt noch viele offene Probleme in diesem Gebiet. Deshalb wurde eine neue Forschungskonferenz in diesem Gebiet im Januar 2007 und ein gehalten

die Liste von offenen Problemen wird von Joseph Miller und Andre Nies aufrechterhalten.

Frequenzberechnung

Dieser Zweig der recursion Theorie hat die folgende Frage analysiert: Für die feste M und n mit 0 < M < n, für die Funktionen A es möglich ist, für jeden verschiedenen n zu rechnen, gibt x, x..., x ein Tupel von n Nummern y, y..., y solch ein, dass mindestens die M der Gleichungen (x) = y wahr ist. Solche Sätze sind als (M, n) - rekursive Sätze bekannt. Das erste Hauptergebnis in diesem Zweig der Recursion Theorie ist das Ergebnis von Trakhtenbrot, dass ein Satz berechenbar ist, wenn es (M, n) - rekursiv für eine M, n mit 2 M &gt ist; n. Andererseits sind die halbrekursiven Sätze von Jockusch (die bereits informell vor Jockusch bekannt waren, hat sie 1968 eingeführt), Beispiele eines Satzes, der (M, n) - rekursiv wenn und nur wenn 2 M &lt ist; n + 1. Es gibt unzählbar viele dieser Sätze und auch einiger rekursiv enumerable, aber nichtberechenbarer Sätze dieses Typs. Später hat Degtev eine Hierarchie rekursiv enumerable Sätze eingesetzt, die (1, n + 1) - rekursiv, aber nicht (1, n) - rekursiv sind. Nach einer langen Phase der Forschung durch russische Wissenschaftler ist dieses Thema wiederverbreitet im Westen durch die These von Beigel auf begrenzten Abfragen geworden, die sich verbunden haben, hat die Frequenzberechnung zum obengenannten erwähnten reducibilities und andere zusammenhängende Begriffe begrenzt. Eines der Hauptergebnisse war die Cardinality Theorie von Kummer, die feststellt, dass ein Satz A wenn und nur berechenbar ist, wenn es einen solchen n gibt, dass ein Algorithmus für jedes Tupel von n verschiedenen Zahlen bis zu n viele mögliche Wahlen des cardinality dieses Satzes von n mit A durchgeschnittenen Zahlen aufzählt; diese Wahlen müssen den wahren cardinality enthalten, aber mindestens einen falschen auslassen.

Induktive Schlussfolgerung

Das ist der recursion-theoretische Zweig, Theorie zu erfahren. Es basiert auf dem Modell von Gold des Lernens in der Grenze von 1967 und hat seitdem immer mehr Modelle des Lernens entwickelt. Das allgemeine Drehbuch ist der folgende: In Anbetracht einer Klasse S von berechenbaren Funktionen, ist dort ein Anfänger (d. h. rekursiv funktionell) der Produktionen für jeden Eingang der Form (f (0), f (1)..., f (n)) eine Hypothese. Ein Anfänger M erfährt eine Funktion f, wenn fast alle Hypothesen derselbe Index e von f in Bezug auf vorher sind, hat sich über das annehmbare Numerieren aller berechenbaren Funktionen geeinigt; M erfährt S, wenn M jeden f in S erfährt. Grundlegende Ergebnisse bestehen darin, dass alle rekursiv enumerable Klassen von Funktionen erlernbar sind, während die Klasse REC aller berechenbaren Funktionen nicht erlernbar ist. Viele zusammenhängende Modelle sind betrachtet worden, und auch das Lernen von Klassen rekursiv enumerable Sätze von positiven Daten ist ein Thema, das vom Pionierpapier von Gold 1967 vorwärts studiert ist.

Generalisationen der Berechenbarkeit von Turing

Theorie von Recursion schließt die Studie von verallgemeinerten Begriffen dieses Feldes wie Arithmetik reducibility, hyperarithmetischer reducibility und α-recursion Theorie, wie beschrieben, durch Säcke (1990) ein. Diese verallgemeinerten Begriffe schließen reducibilities ein, der durch Maschinen von Turing nicht durchgeführt werden kann, aber dennoch natürliche Generalisationen von Turing reducibility ist. Diese Studien schließen Annäherungen ein, um die analytische Hierarchie zu untersuchen, die sich von der arithmetischen Hierarchie durch das Erlauben der Quantifizierung über Sätze von natürlichen Zahlen zusätzlich zur Quantifizierung über individuelle Zahlen unterscheidet. Diese Gebiete werden mit den Theorien der Gut-Einrichtung und Bäume verbunden; zum Beispiel ist der Satz aller Indizes von rekursiven (nichtbinären) Bäumen ohne unendliche Zweige für das Niveau der analytischen Hierarchie abgeschlossen. Sowohl Turing reducibility als auch hyperarithmetischer reducibility sind im Feld der wirksamen beschreibenden Mengenlehre wichtig. Der noch allgemeinere Begriff von Graden von constructibility wird in der Mengenlehre studiert.

Dauernde Berechenbarkeitstheorie

Die Berechenbarkeitstheorie für die Digitalberechnung wird gut entwickelt. Berechenbarkeitstheorie wird für die analoge Berechnung weniger gut entwickelt, die in analogen Computern, analoger Signalverarbeitung, analoger Elektronik, Nervennetzen und dauernd-maliger Steuerungstheorie vorkommt, die durch Differenzialgleichungen und dauernde dynamische Systeme modelliert ist.

Beziehungen zwischen definability, Beweis und Berechenbarkeit

Es gibt nahe Beziehungen zwischen dem Grad von Turing von einer Reihe von natürlichen Zahlen und der Schwierigkeit (in Bezug auf die arithmetische Hierarchie) vom Definieren, die das Verwenden einer Formel der ersten Ordnung setzen. Eine solche Beziehung wird genau durch den Lehrsatz des Postens gemacht. Eine schwächere Beziehung wurde von Kurt Gödel in den Beweisen seines Vollständigkeitslehrsatzes und Unvollständigkeitslehrsätze demonstriert. Die Beweise von Gödel zeigen, dass der Satz von logischen Folgen einer wirksamen Theorie der ersten Ordnung rekursiv enumerable Satz ist, und dass, wenn die Theorie stark genug ist, dieser Satz unberechenbar sein wird. Ähnlich kann der indefinability Lehrsatz von Tarski sowohl in Bezug auf definability als auch in Bezug auf die Berechenbarkeit interpretiert werden.

Theorie von Recursion wird auch mit der zweiten Ordnungsarithmetik, einer formellen Theorie von natürlichen Zahlen und den Sätzen von natürlichen Zahlen verbunden. Die Tatsache, dass bestimmte Sätze berechenbar oder häufig relativ berechenbar sind, deutet an, dass diese Sätze in schwachen Subsystemen der zweiten Ordnungsarithmetik definiert werden können. Das Programm der Rückmathematik verwendet diese Subsysteme, um die weithin bekannten mathematischen Lehrsätzen innewohnende Nichtberechenbarkeit zu messen. Simpson (1999) bespricht viele Aspekte der zweiten Ordnung arithmetische und Rückmathematik.

Das Feld der Probetheorie schließt die Studie der Arithmetik der zweiten Ordnung und Arithmetik von Peano, sowie formellen Theorien der natürlichen Zahlen ein, die schwächer sind als Arithmetik von Peano. Eine Methode, die Kraft dieser schwachen Systeme zu klassifizieren, ist durch das Charakterisieren, welche berechenbare Funktionen sich das System erweisen kann, ganz zu sein (sieh Fairtlough und Wainer (1998)). Zum Beispiel in der primitiven rekursiven Arithmetik ist jede berechenbare Funktion, die nachweisbar ganz ist, rekursiv wirklich primitiv, während Arithmetik von Peano beweist, dass Funktionen wie die Funktion von Ackerman, die rekursiv nicht primitiv sind, ganz sind. Nicht jede berechenbare Gesamtfunktion ist in der Arithmetik von Peano jedoch nachweisbar ganz; ein Beispiel solch einer Funktion wird durch den Lehrsatz von Goodstein zur Verfügung gestellt.

Name des Themas

Das Feld der mathematischen Logik, die sich mit Berechenbarkeit und seinen Generalisationen befasst, ist "recursion Theorie" seit seinen frühen Tagen genannt worden. Robert I. Soare, ein prominenter Forscher im Feld, hat vorgehabt (Soare 1996), dass das Feld "Berechenbarkeitstheorie" stattdessen genannt werden sollte. Er behauptet, dass die Fachsprache von Turing mit dem "berechenbaren" Wort natürlicher und weiter verstanden ist als die Fachsprache mit dem Wort "rekursiv" eingeführt von Kleene. Viele zeitgenössische Forscher haben begonnen, diese abwechselnde Fachsprache zu verwenden. Diese Forscher verwenden auch Fachsprache wie teilweise berechenbare Funktion und berechenbar enumerable (c.e). Satz statt der teilweisen rekursiven Funktion und rekursiv enumerable (r.e). Satz. Nicht alle Forscher sind jedoch, wie erklärt, durch überzeugt gewesen

Fortnow und Simpson.

Einige Kommentatoren behaupten, dass sowohl die Namen recursion Theorie als auch Berechenbarkeitstheorie scheitern, die Tatsache zu befördern, dass die meisten in der recursion Theorie studierten Gegenstände nicht berechenbar sind.

Rogers (1967) hat vorgeschlagen, dass ein Schlüsseleigentum der recursion Theorie darin besteht, dass seine Ergebnisse und Strukturen invariant unter berechenbaren Bijektionen auf den natürlichen Zahlen sein sollten (dieser Vorschlag stützt sich auf die Ideen vom Programm von Erlangen in der Geometrie). Die Idee besteht darin, dass eine berechenbare Bijektion bloß Zahlen in einem Satz umbenennt, anstatt jede Struktur im Satz viel anzuzeigen, weil eine Folge des Euklidischen Flugzeugs keinen geometrischen Aspekt von Linien gestützt es ändert. Da irgendwelche zwei unendlichen berechenbaren Sätze durch eine berechenbare Bijektion verbunden werden, identifiziert dieser Vorschlag alle unendlichen berechenbaren Sätze (die begrenzten berechenbaren Sätze werden als trivial angesehen). Gemäß Rogers sind die Sätze von Interesse in der recursion Theorie die nichtberechenbaren Sätze, die in Gleichwertigkeitsklassen durch berechenbare Bijektionen der natürlichen Zahlen verteilt sind.

Berufsorganisationen

Die Hauptberufsorganisation für die recursion Theorie ist die Vereinigung für die Symbolische Logik, die mehrere Forschungskonferenzen jedes Jahr hält. Die zwischendisziplinarische Forschungsvereinigung Computability in Europe (CiE) organisiert auch eine Reihe von jährlichen Konferenzen. CiE 2012 wird die hundertjährige Konferenz von Turing sein, die in Cambridge als ein Teil des Jahres von Alan Turing gehalten ist.

Siehe auch

• Recursion (Informatik)
• Berechenbarkeitslogik
• Problem von Transcomputational

Referenzen

Studentenniveau-Texte

:* S. B. Cooper, 2004. Computability Theory, Chapman & Hall/CRC. Internationale Standardbuchnummer 1-58488-237-9

:* N. Cutland, 1980. Berechenbarkeit, Eine Einführung in die rekursive Funktionstheorie, Universität von Cambridge Presse. Internationale Standardbuchnummer 0-521-29465-7

:* Y. Matiyasevich, 1993. Das zehnte Problem von Hilbert, MIT Presse. Internationale Standardbuchnummer 0-262-13295-8

Fortgeschrittene Texte

:* S. Jain, D. Osherson, J. Royer und A. Sharma, 1999. Systeme, die, eine Einführung ins Lernen der Theorie, der zweiten Ausgabe, des Buches von Bradford erfahren. Internationale Standardbuchnummer 0-262-10077-0

:* S. Kleene, 1952. Einführung in Metamathematics, Nordholland (11. Druck; 6. Druck hat Anmerkungen hinzugefügt). Internationale Standardbuchnummer 0 7204 2103 9

:* M. Lerman, 1983. Grade der Unlösbarkeit, Perspektiven in der Mathematischen Logik, Springer-Verlag. Internationale Standardbuchnummer 3-540-12155-2.

:* Andre Nies, 2009. Berechenbarkeit und Zufälligkeit, Presse der Universität Oxford, 447 Seiten. Internationale Standardbuchnummer 978-0-19-923076-1.

:* P. Odifreddi, 1989. Klassische Recursion Theorie, Nordholland. Internationale Standardbuchnummer 0-444-87295-7

:* P. Odifreddi, 1999. Klassische Recursion Theorie, Band II, Elsevier. Internationale Standardbuchnummer 0 444 50205 X

:* H. Rogers der Jüngere. 1967. Die Theorie von Rekursiven Funktionen und Wirksamer Berechenbarkeit, zweiter Ausgabe 1987, MIT Presse. Internationale Standardbuchnummer 0-262-68052-1 (Paperback), internationale Standardbuchnummer 0-07-053522-1

:* G Säcke, 1990. Höher Recursion Theorie, Springer-Verlag. Internationale Standardbuchnummer 3-540-19305-7

:* S. G. Simpson, 1999. Subsysteme der Zweiten Ordnungsarithmetik, Springers-Verlag. Internationale Standardbuchnummer 3-540-64882-8

:* R. I. Soare, 1987. Rekursiv Enumerable Sätze und Grade, Perspektiven in der Mathematischen Logik, Springer-Verlag. Internationale Standardbuchnummer 0-387-15299-7.

Überblick-Papiere und Sammlungen

:* K. Ambos-Spione und P. Fejer, 2006. "Grade der Unlösbarkeit." Unveröffentlichter Vorabdruck.

:* H. Enderton, 1977. "Elemente der Recursion Theorie." Handbuch der Mathematischen Logik, die von J. Barwise, Nordholland (1977), Seiten 527-566 editiert ist. Internationale Standardbuchnummer 0 7204 2285 X

:* Y. L. Ershov, S. S. Goncharov, A. Nerode und J. B. Remmel, 1998. Handbuch der Rekursiven Mathematik, Nordholland (1998). Internationale Standardbuchnummer 0 7204 2285 X

:* M. Fairtlough und S. Wainer, 1998. "Hierarchien Nachweisbar Rekursiver Funktionen". Im Handbuch der Probetheorie, die durch S editiert ist. Kuss, Elsevier (1998).

:* R. I. Soare, 1996. Berechenbarkeit und recursion, Meldung der Symbolischen Logik v. 2 Seiten 284-321.

Forschungsarbeiten und Sammlungen

:* Burgin, M. und Klinger, A. "Erfahrung, Generationen und Grenzen im Maschinenlernen." Theoretische Informatik v. 317, Nr. 1/3, 2004, Seiten 71-91

:* A. Kirche, 1936a. "Ein unlösbares Problem der elementaren Zahlentheorie." Amerikanische Zeitschrift der Mathematik v. 58, Seiten 345-363. Nachgedruckt "im Unentscheidbaren", der Hrsg. von M. Davis, 1965.

:* A. Kirche, 1936b. "Ein Zeichen auf Entscheidungsproblem." Zeitschrift der Symbolischen Logik v. 1, n. 1, und v. 3, n. 3. Nachgedruckt "im Unentscheidbaren", der Hrsg. von M. Davis, 1965.

:* M. Davis, Hrsg., 1965. Die Unentscheidbar-grundlegenden Papiere auf Unentscheidbaren Vorschlägen, Unlösbaren Problemen und Berechenbaren Funktionen, Raben, New York. Nachdruck, Dover, 2004. Internationale Standardbuchnummer 0-486-43228-9

:* R. M. Friedberg, 1958. "Drei Lehrsätze auf der rekursiven Enumeration:I. Zergliederung, II. Maximaler Satz, III. Enumeration ohne Wiederholung." Die Zeitschrift der Symbolischen Logik, v. 23, Seiten 309-316.

:* E. M Gold, 1967. "Sprachidentifizierung in der Grenze". Information und Kontrolle, Band 10, Seiten 447-474.

:* L. Harrington und R. I. Soare, 1991. "Das Programm des Postens und unvollständig rekursiv enumerable Sätze", Verhandlungen der Nationalen Akademie von Wissenschaften der USA, des Bands 88, der Seiten 10242 — 10246.

:* C. Jockusch der Jüngere, "Halbrekursive Sätze und positiver reducibility", Trans. Amer. Mathematik. Soc. 137 (1968) 420-436

:* S. C. Kleene und E. L. Post, 1954. "Das obere Halbgitter von Graden der rekursiven Unlösbarkeit." Annalen der Mathematik v. 2 n. 59, 379-407.

:* J. Myhill, 1956. "Das Gitter rekursiv enumerable Sätze." Die Zeitschrift der Symbolischen Logik, v. 21, Seiten 215-220.

:* E. Posten, 1944, "Rekursiv enumerable Sätze von positiven ganzen Zahlen und ihren Entscheidungsproblemen", Meldung der amerikanischen Mathematischen Gesellschaft, des Bands 50, der Seiten 284-316.

:* E. Posten, 1947. "Rekursive Unlösbarkeit eines Problems von Thue." Zeitschrift der Symbolischen Logik v. 12, Seiten 1-11. Nachgedruckt "im Unentscheidbaren", der Hrsg. von M. Davis, 1965.

:*

:* T. Slaman und W. H. Woodin, 1986. "Definability in den Graden von Turing." Illinois J. Mathematik. v. 30 n. 2, Seiten 320-334.

:* R. I. Soare, 1974. "Automorphisms des Gitters rekursiv enumerable Sätze, erster Teil: Maximale Sätze." Annalen der Mathematik, v. 100, Seiten 80-120.

:* A. Turing, 1937. "Auf berechenbaren Zahlen, mit einer Anwendung auf Entscheidungsproblem." Verhandlungen der Londoner Mathematik-Gesellschaft, ser. 2 v. 42, Seiten 230-265. Korrekturen ibd. v. 43 (1937) Seiten 544-546. Nachgedruckt "im Unentscheidbaren", der Hrsg. von M. Davis, 1965. PDF von comlab.ox.ac.uk

:* A. Turing, 1939. "Systeme der Logik auf Ordnungszahlen gestützt." Verhandlungen der Londoner Mathematik-Gesellschaft, ser. 2 v. 45, Seiten 161-228. Nachgedruckt "im Unentscheidbaren", der Hrsg. von M. Davis, 1965.

Links

• Vereinigung für die Symbolische Logikeinstiegsseite
• Berechenbarkeit in der europäischen Einstiegsseite
• Webpage auf dem Recursion Theorie-Kurs am Absolventenniveau mit etwa 100 Seiten des Vortrags bemerkt
• Vortrag der deutschen Sprache bemerkt auf der induktiven Schlussfolgerung