Berechenbarkeitstheorie

Beginnend mit der oben beschriebenen Theorie der rekursiven Mengen und Funktionen ist das Gebiet der Rekursionstheorie gewachsen und umfasst das Studium vieler eng verwandter Themen. Dies sind keine unabhängigen Forschungsbereiche: Jeder dieser Bereiche zieht Ideen und Ergebnisse aus den anderen, und die meisten Rekursionstheoretiker sind mit den meisten von ihnen vertraut.

Relative Berechenbarkeit und die Turing-Gradebearbeiten

Die Rekursionstheorie in der mathematischen Logik hat sich traditionell auf die relative Berechenbarkeit konzentriert, eine Verallgemeinerung der Turing-Berechenbarkeit, die mit Oracle Turing Machines definiert wurde und von Turing (1939) eingeführt wurde. Eine Orakel-Turing-Maschine ist ein hypothetisches Gerät, das nicht nur die Aktionen einer regulären Turing-Maschine ausführt, sondern auch Fragen an ein Orakel stellen kann, bei dem es sich um eine bestimmte Menge natürlicher Zahlen handelt. Die Oracle-Maschine darf nur Fragen der Form “Ist n in der Oracle-Menge?”. Jede Frage wird sofort richtig beantwortet, auch wenn das Oracle-Set nicht berechenbar ist. Somit kann eine Oracle-Maschine mit einem nicht berechenbaren Oracle Mengen berechnen, die eine Turing-Maschine ohne Oracle nicht berechnen kann.

Informell ist eine Menge natürlicher Zahlen A Turing reduzierbar auf eine Menge B, wenn es eine Oracle-Maschine gibt, die korrekt angibt, ob Zahlen in A sind, wenn sie mit B als Oracle-Menge ausgeführt werden (in diesem Fall wird die Menge A auch als (relativ) berechenbar von B und rekursiv in B ). Wenn eine Menge A Turing-reduzierbar auf eine Menge B und B Turing-reduzierbar auf A ist, dann sollen die Mengen den gleichen Turing-Grad haben (auch Grad der Unlösbarkeit genannt). Der Turing-Grad einer Menge gibt ein genaues Maß dafür, wie unkomprimierbar die Menge ist.

Die natürlichen Beispiele für Mengen, die nicht berechenbar sind, einschließlich vieler verschiedener Mengen, die Varianten des Halteproblems codieren, haben zwei Eigenschaften gemeinsam:

1. Sie sind rekursiv aufzählbar, und
2. Jeder kann über eine Viele-Eins-Reduktion in einen anderen übersetzt werden. Das heißt, bei solchen Mengen A und B gibt es eine insgesamt berechenbare Funktion f , so dass A = {x : f(x) ∈ B} . Diese Mengen werden als Many-One-Äquivalent (oder m-Äquivalent) bezeichnet.

Viele-Eins-Reduktionen sind “stärker” als Turing-Reduktionen: Wenn eine Menge A viele-Eins auf eine Menge B reduzierbar ist, dann ist A Turing reduzierbar auf B , aber das Gegenteil gilt nicht immer. Obwohl die natürlichen Beispiele für nicht berechenbare Mengen alle Viele-Eins-Äquivalente sind, ist es möglich, rekursiv aufzählbare Mengen A und B so zu konstruieren, dass A Turing-reduzierbar auf B ist, aber nicht viele-Eins-reduzierbar auf B. Es kann gezeigt werden, dass jede rekursiv aufzählbare Menge um ein Vielfaches auf das Halteproblem reduzierbar ist, und somit ist das Halteproblem die komplizierteste rekursiv aufzählbare Menge in Bezug auf die Viele-Eins-Reduzierbarkeit und in Bezug auf die Turing-Reduzierbarkeit. Post (1944) fragte, ob jede rekursiv aufzählbare Menge entweder berechenbar oder Turing-äquivalent zum Halteproblem ist, dh ob es keine rekursiv aufzählbare Menge mit einem Turing-Grad zwischen diesen beiden gibt.

Als Zwischenergebnisse definierte Post natürliche Typen rekursiv aufzählbarer Mengen wie die einfachen, hypersimplen und hyperhypersimplen Mengen. Post zeigte, dass diese Mengen streng zwischen den berechenbaren Mengen und dem Halteproblem in Bezug auf die Viele-Eins-Reduzierbarkeit liegen. Post zeigte auch, dass einige von ihnen unter anderen Reduzierbarkeitsbegriffen, die stärker sind als die Turing-Reduzierbarkeit, streng intermediär sind. Aber Post ließ das Hauptproblem der Existenz von rekursiv aufzählbaren Sätzen von mittlerem Turing-Grad offen; Dieses Problem wurde als Post-Problem bekannt. Nach zehn Jahren zeigten Kleene und Post 1954, dass es mittlere Turing-Grade zwischen denen der berechenbaren Mengen und dem Halteproblem gibt, aber sie konnten nicht zeigen, dass einer dieser Grade eine rekursiv aufzählbare Menge enthält. Sehr bald darauf lösten Friedberg und Muchnik das Problem von Post unabhängig voneinander, indem sie die Existenz rekursiv aufzählbarer Mengen mittleren Grades feststellten. Dieses bahnbrechende Ergebnis eröffnete eine umfassende Untersuchung der Turing-Grade der rekursiv aufzählbaren Mengen, die sich als sehr kompliziert und nicht trivial herausstellten Struktur.

Es gibt unzählige Mengen, die nicht rekursiv aufzählbar sind, und die Untersuchung der Turinggrade aller Mengen ist in der Rekursionstheorie ebenso zentral wie die Untersuchung der rekursiv aufzählbaren Turinggrade. Viele Grade mit speziellen Eigenschaften wurden konstruiert: hyperimmunfreie Grade, bei denen jede relativ zu diesem Grad berechenbare Funktion durch eine (nicht relativierte) berechenbare Funktion majorisiert wird; hohe Grade, relativ zu denen man eine Funktion f berechnen kann, die jede berechenbare Funktion g in dem Sinne dominiert, dass es eine Konstante c gibt, die von g abhängt, so dass g (x) < f (x) für alle x > c; zufällige Grade, die algorithmisch zufällige Mengen enthalten; 1-generische Grade von 1-generischen Mengen; und die Grade unterhalb des Halteproblems von grenzrekursiven Mengen.

Das Studium beliebiger (nicht unbedingt rekursiv aufzählbarer) Turing-Grade beinhaltet das Studium des Turing-Sprungs. Bei einer gegebenen Menge A ist der Turing-Sprung von A eine Menge natürlicher Zahlen, die eine Lösung für das Halteproblem für Oracle-Turing-Maschinen codieren, die mit Oracle A . Der Turing-Sprung einer Menge ist immer von höherem Turing-Grad als die ursprüngliche Menge, und ein Satz von Friedburg zeigt, dass jede Menge, die das Halteproblem berechnet, als Turing-Sprung einer anderen Menge erhalten werden kann. Der Satz von Post stellt eine enge Beziehung zwischen der Turing-Sprungoperation und der arithmetischen Hierarchie her, die eine Klassifizierung bestimmter Teilmengen der natürlichen Zahlen basierend auf ihrer Definierbarkeit in der Arithmetik darstellt.

Viele neuere Forschungen zu Turing-Abschlüssen haben sich auf die Gesamtstruktur der Menge von Turing-Abschlüssen und der Menge von Turing-Abschlüssen konzentriert, die rekursiv aufzählbare Mengen enthalten. Ein tiefer Satz von Shore und Slaman (1999) besagt, dass die Funktion, die einen Grad x auf den Grad seines Turing-Sprungs abbildet, in der partiellen Reihenfolge der Turing-Grade definierbar ist. Eine aktuelle Umfrage von Ambos-Spies und Fejer (2006) gibt einen Überblick über diese Forschung und ihre historische Entwicklung.

Andere Reduzierbarkeitenbearbeiten

Ein fortlaufendes Forschungsgebiet in der Rekursionstheorie untersucht andere Reduzierbarkeitsbeziehungen als die Turing-Reduzierbarkeit. Post (1944) führte mehrere starke Reduzierbarkeiten ein, die so genannt wurden, weil sie eine Wahrheitstabellenreduzierbarkeit implizieren. Eine Turing-Maschine, die eine starke Reduzierbarkeit implementiert, berechnet eine Gesamtfunktion, unabhängig davon, mit welchem Oracle sie dargestellt wird. Schwache Reduzierbarkeiten sind solche, bei denen ein Reduktionsprozess nicht für alle Orakel enden kann; Turing Reduzierbarkeit ist ein Beispiel.

Die starken Reduzierungen umfassen:

Eins-Eins-Reduzierbarkeit A ist eins-eins-reduzierbar (oder 1-reduzierbar) auf B, wenn es eine insgesamt berechenbare injektive Funktion f gibt, so dass jedes n genau dann in A ist, wenn f (n) in B ist. A ist many-one reduzierbar (oder m-reduzierbar) auf B, wenn es eine berechenbare Gesamtfunktion f gibt, so dass jedes n genau dann in A ist, wenn f (n) in B ist. Reduzierbarkeit der Wahrheitstabelle A ist auf B reduzierbar, wenn A über eine Oracle-Turing-Maschine, die eine Gesamtfunktion berechnet, unabhängig vom angegebenen Oracle auf B reduzierbar ist. Aufgrund der Kompaktheit des Cantor-Raums entspricht dies der Aussage, dass das Orakel dem Orakel gleichzeitig eine einzige Liste von Fragen (nur abhängig von der Eingabe) vorlegt und dann, nachdem es ihre Antworten gesehen hat, eine Ausgabe erstellen kann, ohne zusätzliche Fragen zu stellen, unabhängig von der Antwort des Orakels auf die ersten Abfragen. Viele Varianten der Wahrheitstabellenreduzierbarkeit wurden ebenfalls untersucht.

Weitere Reduzierungen (positiv, disjunktiv, konjunktiv, linear und ihre schwachen und begrenzten Versionen) werden im Artikel Reduktion (Rekursionstheorie) diskutiert.

Die Hauptforschung zu starken Reduzierungen bestand darin, ihre Theorien sowohl für die Klasse aller rekursiv aufzählbaren Mengen als auch für die Klasse aller Teilmengen der natürlichen Zahlen zu vergleichen. Darüber hinaus wurden die Beziehungen zwischen den Reduzierbarkeiten untersucht. Zum Beispiel ist bekannt, dass jeder Turing-Grad entweder ein Wahrheitstabellengrad oder die Vereinigung unendlich vieler Wahrheitstabellengrade ist.

Reduzierbarkeiten, die schwächer sind als die Turing-Reduzierbarkeit (dh Reduzierbarkeiten, die durch die Turing-Reduzierbarkeit impliziert werden), wurden ebenfalls untersucht. Die bekanntesten sind die arithmetische Reduzierbarkeit und die hyperarithmetische Reduzierbarkeit. Diese Reduzierbarkeiten sind eng mit der Definierbarkeit über das Standardmodell der Arithmetik verbunden.

Satz von Rice und die arithmetische Hierarchiebearbeiten

Rice zeigte, dass für jede nichttriviale Klasse C (die einige, aber nicht alle r.e.-Mengen enthält) die Indexmenge E = {e: die eth r.e. menge, die wir in C} hat die Eigenschaft, dass entweder das Halteproblem oder sein Komplement um ein Vielfaches auf E reduzierbar ist, dh mit einer um ein Vielfaches reduzierten Zahl auf E abgebildet werden kann (siehe Satz von Rice für weitere Details). Viele dieser Indexsätze sind jedoch noch komplizierter als das Halteproblem. Diese Art von Mengen kann mithilfe der arithmetischen Hierarchie klassifiziert werden. Beispielsweise befindet sich die Indexmenge FIN der Klasse aller endlichen Mengen auf der Ebene Σ2, die Indexmenge REC der Klasse aller rekursiven Mengen auf der Ebene Σ3, die Indexmenge COFIN aller cofiniten Mengen ebenfalls auf der Ebene Σ3 und die Indexmenge COMP der Klasse aller Turing-vollständigen Mengen Σ4. Diese Hierarchieebenen sind induktiv definiert, Σn+1 enthält nur alle Mengen, die relativ zu Σn rekursiv aufzählbar sind; Σ1 enthält die rekursiv aufzählbaren Mengen. Die hier angegebenen Indexsätze sind sogar für ihre Ebenen vollständig, dh alle Sätze in diesen Ebenen können viele sein – eine auf die angegebenen Indexsätze reduziert.

Reverse mathematicsEdit

Das Programm der umgekehrten Mathematik fragt, welche Mengenexistenzaxiome notwendig sind, um bestimmte Sätze der Mathematik in Subsystemen der Arithmetik zweiter Ordnung zu beweisen. Diese Studie wurde von Harvey Friedman initiiert und von Stephen Simpson und anderen im Detail untersucht; Simpson (1999) gibt eine detaillierte Diskussion des Programms. Die fraglichen Mengenexistenzaxiome entsprechen informell Axiomen, die besagen, dass die Potenzmenge der natürlichen Zahlen unter verschiedenen Reduzierbarkeitsbegriffen geschlossen ist. Das schwächste Axiom, das in der umgekehrten Mathematik untersucht wird, ist das rekursive Verständnis, das besagt, dass die Potenz der Naturals unter Turing Reduzierbarkeit geschlossen ist.

NumberingsEdit

Eine Nummerierung ist eine Aufzählung von Funktionen; sie hat zwei Parameter, e und x und gibt den Wert der e-ten Funktion in der Nummerierung am Eingang x aus. Nummerierungen können partiell rekursiv sein, obwohl einige ihrer Mitglieder insgesamt rekursiv sind, dh berechenbare Funktionen. Zulässige Nummerierungen sind solche, in die alle anderen übersetzt werden können. Eine Friedberg-Nummerierung (benannt nach ihrem Entdecker) ist eine Eins-Eins-Nummerierung aller partialrekursiven Funktionen; es ist notwendigerweise keine zulässige Nummerierung. Spätere Forschungen befassten sich auch mit Nummerierungen anderer Klassen wie Klassen rekursiv aufzählbarer Mengen. Goncharov entdeckte zum Beispiel eine Klasse von rekursiv aufzählbaren Mengen, für die die Nummerierungen in Bezug auf rekursive Isomorphismen in genau zwei Klassen fallen.

Die Prioritätsmethodeedit

Weitere Erläuterungen finden Sie im Abschnitt Post-Problem und die Prioritätsmethode im Artikel Turing-Grad.

Das Problem von Post wurde mit einer Methode namens priority-Methode gelöst; Ein Beweis, der diese Methode verwendet, wird als priority-Argument bezeichnet. Diese Methode wird hauptsächlich verwendet, um rekursiv aufzählbare Mengen mit bestimmten Eigenschaften zu erstellen. Um diese Methode zu verwenden, werden die gewünschten Eigenschaften der zu konstruierenden Menge in eine unendliche Liste von Zielen unterteilt, die als Anforderungen bezeichnet werden, so dass die Erfüllung aller Anforderungen dazu führt, dass die konstruierte Menge die gewünschten Eigenschaften aufweist. Jede Anforderung wird einer natürlichen Zahl zugewiesen, die die Priorität der Anforderung darstellt; So wird 0 der wichtigsten Priorität, 1 der zweitwichtigsten usw. zugewiesen. Der Satz wird dann in Stufen konstruiert, wobei jede Stufe versucht, eine oder mehrere der Anforderungen zu erfüllen, indem entweder Zahlen zum Satz hinzugefügt oder Zahlen aus dem Satz verbannt werden, so dass der endgültige Satz die Anforderung erfüllt. Es kann vorkommen, dass die Erfüllung einer Anforderung dazu führt, dass eine andere unbefriedigt wird; Die Prioritätsreihenfolge wird verwendet, um zu entscheiden, was in einem solchen Fall zu tun ist.

Prioritätsargumente wurden verwendet, um viele Probleme in der Rekursionstheorie zu lösen, und wurden basierend auf ihrer Komplexität in eine Hierarchie eingeteilt (Soare 1987). Da komplexe Prioritätsargumente technisch und schwer zu befolgen sein können, wurde es traditionell als wünschenswert angesehen, Ergebnisse ohne Prioritätsargumente zu beweisen oder zu prüfen, ob Ergebnisse, die mit Prioritätsargumenten bewiesen wurden, auch ohne sie bewiesen werden können. Zum Beispiel veröffentlichte Kummer ein Papier über einen Beweis für die Existenz von Friedberg-Nummerierungen ohne Verwendung der Prioritätsmethode.

Das Gitter der rekursiv aufzählbaren Mengenbearbeiten

Als Post den Begriff einer einfachen Menge als r.e.-Menge mit einem unendlichen Komplement definierte, das keine unendliche r.e. set, begann er, die Struktur der rekursiv aufzählbaren Mengen unter Einbeziehung zu studieren. Dieses Gitter wurde zu einer gut untersuchten Struktur. Rekursive Mengen können in dieser Struktur durch das grundlegende Ergebnis definiert werden, dass eine Menge genau dann rekursiv ist, wenn die Menge und ihr Komplement beide rekursiv aufzählbar sind. Unendliche r.e. Mengen haben immer unendliche rekursive Teilmengen; Auf der anderen Seite existieren einfache Mengen, haben aber keine coinfinite rekursive Obermenge. Post (1944) führte bereits hypersimple und hyperhypersimple Mengen ein; später wurden maximale Mengen konstruiert, die r.e. Sets sind, so dass jeder r.e. Obermenge ist entweder eine endliche Variante der gegebenen maximalen Menge oder ist co-endlich. Die ursprüngliche Motivation von Post bei der Untersuchung dieses Gitters bestand darin, einen strukturellen Begriff zu finden, so dass jede Menge, die diese Eigenschaft erfüllt, weder im Turing-Grad der rekursiven Mengen noch im Turing-Grad des Halteproblems liegt. Post fand eine solche Eigenschaft nicht und die Lösung seines Problems wandte stattdessen Prioritätsmethoden an; Harrington und Soare (1991) fanden schließlich eine solche Eigenschaft.

Automorphismusproblemebearbeiten

Eine weitere wichtige Frage ist die Existenz von Automorphismen in rekursionstheoretischen Strukturen. Eine dieser Strukturen ist die einer rekursiv aufzählbaren Mengen unter Einschluss modulo finite difference; In dieser Struktur ist A genau dann unter B, wenn die Mengendifferenz B − A endlich ist. Maximale Mengen (wie im vorherigen Absatz definiert) haben die Eigenschaft, dass sie nicht automorph zu nicht-maximalen Mengen sein können, das heißt, wenn es einen Automorphismus der rekursiven aufzählbaren Mengen unter der gerade erwähnten Struktur gibt, dann wird jede maximale Menge einer anderen maximalen Menge zugeordnet. Soare (1974) zeigte, dass auch das Gegenteil gilt, dh alle zwei maximalen Mengen sind automorph. Die maximalen Mengen bilden also eine Umlaufbahn, dh jeder Automorphismus bewahrt die Maximalität und zwei beliebige Maximalmengen werden durch einen Automorphismus ineinander umgewandelt. Harrington gab ein weiteres Beispiel für eine automorphe Eigenschaft: die der kreativen Mengen, die Mengen, die viele sind -eins entspricht dem Halteproblem.

Neben dem Gitter rekursiv aufzählbarer Mengen werden Automorphismen auch für die Struktur der Turinggrade aller Mengen sowie für die Struktur der Turinggrade von r.e.-Mengen untersucht. In beiden Fällen, Cooper behauptet, nichttriviale Automorphismen konstruiert zu haben, die einige Grade anderen Graden zuordnen; diese Konstruktion wurde jedoch nicht verifiziert und einige Kollegen glauben, dass die Konstruktion Fehler enthält und dass die Frage, ob es einen nichttrivialen Automorphismus der Turing-Grade gibt, immer noch eine der wichtigsten ungelösten Fragen in diesem Bereich ist (Slaman und Woodin 1986, Ambos-Spies und Fejer 2006).

Kolmogorov-Komplexitätbearbeiten

Das Gebiet der Kolmogorov-Komplexität und der algorithmischen Zufälligkeit wurde in den 1960er und 1970er Jahren von Chaitin, Kolmogorov, Levin, Martin-Löf und Solomonoff entwickelt (die Namen sind hier in alphabetischer Reihenfolge angegeben; Ein Großteil der Forschung war unabhängig und die Einheit des Konzepts der Zufälligkeit wurde zu dieser Zeit nicht verstanden). Die Hauptidee besteht darin, eine universelle Turingmaschine U zu betrachten und die Komplexität einer Zahl (oder Zeichenfolge) x als Länge der kürzesten Eingabe p zu messen, so dass U (p) x ausgibt. Dieser Ansatz revolutionierte frühere Methoden, um zu bestimmen, wann eine unendliche Folge (äquivalent, charakteristische Funktion einer Teilmenge der natürlichen Zahlen) zufällig ist oder nicht, indem er einen Begriff der Zufälligkeit für endliche Objekte aufruft. Die Komplexität von Kolmogorov wurde nicht nur Gegenstand unabhängiger Studien, sondern wird auch auf andere Fächer als Instrument zur Erlangung von Beweisen angewendet.In diesem Bereich gibt es noch viele offene Probleme. Aus diesem Grund fand kürzlich im Januar 2007 eine Forschungskonferenz in diesem Bereich statt, und Joseph Miller und Andre Nies führen eine Liste offener Probleme.

Frequenzberechnung

Dieser Zweig der Rekursionstheorie analysierte die folgende Frage: Für feste m und n mit 0 < m < n, für welche Funktionen A ist es möglich, für verschiedene n Eingänge x1, x2, …, xn ein Tupel von n Zahlen y1,y2,…,yn, so dass mindestens m der Gleichungen A(xk) = yk wahr sind. Solche Mengen sind als (m, n) -rekursive Mengen bekannt. Das erste große Ergebnis in diesem Zweig der Rekursionstheorie ist Trakhtenbrots Ergebnis, dass eine Menge berechenbar ist, wenn sie für einige m, n mit 2m > n (m, n) -rekursiv ist. Auf der anderen Seite sind Jockuschs semikursive Mengen (die bereits informell bekannt waren, bevor Jockusch sie 1968 einführte) Beispiele für eine Menge, die genau dann (m, n) -rekursiv ist, wenn 2m < n + 1 . Es gibt unzählige dieser Mengen und auch einige rekursiv aufzählbare, aber nicht berechenbare Mengen dieses Typs. Später etablierte Degtev eine Hierarchie von rekursiv aufzählbaren Mengen, die (1, n + 1) -rekursiv, aber nicht (1, n) -rekursiv sind. Nach einer langen Forschungsphase russischer Wissenschaftler wurde dieses Thema im Westen durch Beigels These über begrenzte Abfragen wieder populär, die die Frequenzberechnung mit den oben genannten begrenzten Reduzierbarkeiten und anderen verwandten Begriffen verband. Eines der Hauptergebnisse war Kummers Kardinalitätstheorie, die besagt, dass eine Menge A genau dann berechenbar ist, wenn es ein n gibt, so dass ein Algorithmus für jedes Tupel von n verschiedenen Zahlen bis zu n viele mögliche Auswahlmöglichkeiten der Kardinalität dieser Menge von n Zahlen aufzählt, die mit a geschnitten werden; diese Entscheidungen müssen die wahre Kardinalität enthalten, aber mindestens eine falsche weglassen.

Induktive Inferenzbearbeiten

Dies ist der rekursionstheoretische Zweig der Lerntheorie. Es basiert auf E. Mark Golds Modell des Lernens in den Usa von 1967 und hat seitdem immer mehr Lernmodelle entwickelt. Das allgemeine Szenario ist das folgende: Gibt es bei einer Klasse S berechenbarer Funktionen einen Lernenden (dh eine rekursive Funktion), der für jede Eingabe der Form (f(0),f(1),…,f(n)) eine Hypothese. Ein Lernender M lernt eine Funktion f, wenn fast alle Hypothesen den gleichen Index e von f in Bezug auf eine zuvor vereinbarte akzeptable Nummerierung aller berechenbaren Funktionen haben; M lernt S, wenn M jedes f in S lernt. Viele verwandte Modelle wurden in Betracht gezogen, und auch das Lernen von Klassen rekursiv aufzählbarer Mengen aus positiven Daten ist ein Thema, das ab Golds Pionierarbeit von 1967 untersucht wurde.

Verallgemeinerungen der Turing-Berechenbarkeitbearbeiten

Die Rekursionstheorie umfasst das Studium verallgemeinerter Begriffe dieses Feldes wie arithmetische Reduzierbarkeit, hyperarithmetische Reduzierbarkeit und α-Rekursionstheorie, wie von Sacks (1990) beschrieben. Diese verallgemeinerten Begriffe umfassen Reduzierbarkeiten, die nicht von Turing-Maschinen ausgeführt werden können, aber dennoch natürliche Verallgemeinerungen der Turing-Reduzierbarkeit sind. Diese Studien umfassen Ansätze zur Untersuchung der analytischen Hierarchie, die sich von der arithmetischen Hierarchie unterscheidet, indem sie zusätzlich zur Quantifizierung einzelner Zahlen eine Quantifizierung über Mengen natürlicher Zahlen ermöglicht. Diese Bereiche sind mit den Theorien der Wohlordnungen und Bäume verbunden; Zum Beispiel ist die Menge aller Indizes rekursiver (nichtbinärer) Bäume ohne unendliche Zweige für die Ebene Π 1 1 {\displaystyle \Pi} vollständig _{1}^{1}}

der analytischen Hierarchie. Sowohl die Turing-Reduzierbarkeit als auch die hyperarithmetische Reduzierbarkeit sind im Bereich der effektiven deskriptiven Mengenlehre wichtig. Der noch allgemeinere Begriff der Konstruktibilitätsgrade wird in der Mengenlehre untersucht.

Kontinuierliche Berechenbarkeitstheorie

Die Berechenbarkeitstheorie für digitale Berechnungen ist gut entwickelt. Die Berechenbarkeitstheorie ist für analoge Berechnungen, die in Analogcomputern, analoger Signalverarbeitung, analoger Elektronik, neuronalen Netzen und zeitkontinuierlicher Steuerungstheorie auftreten und durch Differentialgleichungen und kontinuierliche dynamische Systeme modelliert werden, weniger gut entwickelt (Orponen 1997; Moore 1996).