Die Church-Turing-These bezieht sich auf das Konzept einer effizienten, systematischen oder mechanischen Methode in Logik, Mathematik und Informatik. Sie ist als Beschreibung des intuitiven Begriffs der Berechenbarkeit formuliert und wird in Bezug auf allgemeine rekursive Funktionen häufiger als Church-These bezeichnet. Es bezieht sich auch auf die Theorie der computerberechneten Funktionen. Die These erschien in den 1930er Jahren, als Computer selbst noch nicht existierten. Es wurde später nach dem amerikanischen Mathematiker Alonso Church und seinem britischen Kollegen Alan Turing benannt.
Effizienz der Methode zur Erzielung des Ergebnisses
Das erste Gerät, das einem modernen Computer ähnelte, war die Bombie, eine Maschine des englischen Mathematikers Alan Turing. Es wurde verwendet, um deutsche Nachrichten während des Zweiten Weltkriegs zu entschlüsseln. Aber für seine These und Formalisierung des Konzepts eines Algorithmus verwendete er abstrakte Maschinen, später Turing-Maschinen genannt. Diplomarbeit präsentiertInteresse sowohl für Mathematiker als auch für Programmierer, da diese Idee die Schöpfer der ersten Computer inspirierte.
In der Berechenbarkeitstheorie ist die Church-Turing-These auch als Vermutung über die Natur berechenbarer Funktionen bekannt. Es besagt, dass es für jede algorithmisch berechenbare Funktion auf natürlichen Zahlen eine Turing-Maschine gibt, die sie berechnen kann. Oder anders gesagt, es gibt einen dafür geeigneten Algorithmus. Ein bekanntes Beispiel für die Wirksamkeit dieser Methode ist der Wahrheitstabellentest zur Überprüfung der Tautologie.
Ein Weg, um ein gewünschtes Ergebnis zu erzielen, heißt "effektiv", "systematisch" oder "mechanisch", wenn:
- Die Methode wird durch eine endliche Anzahl exakter Anweisungen spezifiziert, jede Anweisung wird durch eine endliche Anzahl von Zeichen ausgedrückt.
- Es läuft fehlerfrei, bringt in einer bestimmten Anzahl von Schritten das gewünschte Ergebnis.
- Die Methode kann von einem Menschen ohne Hilfe mit jeder anderen Ausrüstung als Papier und Bleistift durchgeführt werden
- Es erfordert kein Verständnis, keine Intuition oder Einfallsreichtum seitens der Person, die die Aktion durchführt
Früher in der Mathematik wurde der informelle Begriff "effektiv berechenbar" verwendet, um sich auf Funktionen zu beziehen, die mit Bleistift und Papier berechnet werden können. Aber der Begriff der algorithmischen Berechenbarkeit war intuitiver als alles Konkrete. Nun zeichnete es sich durch eine Funktion mit natürlichem Argument aus, für die es einen Berechnungsalgorithmus gibt. Eine der Errungenschaften von Alan Turing warDarstellung eines formal exakten Prädikats, mit dessen Hilfe es möglich wäre, das informelle zu ersetzen, wenn die Methode Effizienzbedingung verwendet wird. Church hat dieselbe Entdeckung gemacht.
Grundkonzepte rekursiver Funktionen
Turings Prädikatenwechsel sah auf den ersten Blick anders aus als der von seinem Kollegen vorgeschlagene. Aber im Ergebnis stellten sie sich als äquivalent heraus, in dem Sinne, dass jeder von ihnen denselben Satz mathematischer Funktionen auswählt. Die Church-Turing-These ist die Behauptung, dass diese Menge jede Funktion enthält, deren Werte durch ein Verfahren erh alten werden können, das die Effizienzbedingungen erfüllt. Es gab noch einen weiteren Unterschied zwischen den beiden Entdeckungen. Church betrachtete nur Beispiele für positive ganze Zahlen, während Turing seine Arbeit so beschrieb, dass sie berechenbare Funktionen mit einer integralen oder reellen Variablen abdeckt.
Allgemeine rekursive Funktionen
Churchs ursprüngliche Formulierung besagt, dass die Berechnung mit dem λ-Kalkül durchgeführt werden kann. Dies entspricht der Verwendung generischer rekursiver Funktionen. Die Church-Turing-These deckt mehr Arten von Berechnungen ab als ursprünglich angenommen. Zum Beispiel in Bezug auf zellulare Automaten, Kombinatoren, Registrierungsmaschinen und Substitutionssysteme. 1933 erstellten die Mathematiker Kurt Gödel und Jacques Herbrand eine formale Definition einer Klasse namens allgemeine rekursive Funktionen. Es verwendet Funktionen, bei denen mehr als ein Argument möglich ist.
Erstellen einer Methodeλ-Kalkül
Im Jahr 1936 schuf Alonso Church eine Bestimmungsmethode namens λ-Kalkül. Er wurde mit natürlichen Zahlen in Verbindung gebracht. Innerhalb des λ-Kalküls ermittelte der Wissenschaftler ihre Kodierung. Daher werden sie Kirchennummern genannt. Eine auf natürlichen Zahlen basierende Funktion wurde λ-berechenbar genannt. Es gab eine andere Definition. Die Funktion aus Churchs These heißt unter zwei Bedingungen λ-berechenbar. Die erste klang so: wenn sie auf Kirchenelementen berechnet wurde, und die zweite Bedingung war die Möglichkeit, durch ein Mitglied des λ-Kalküls repräsentiert zu werden.
Ebenfalls 1936, bevor er die Arbeit seines Kollegen studierte, schuf Turing ein theoretisches Modell für die abstrakten Maschinen, die heute nach ihm benannt sind. Sie konnten Berechnungen durchführen, indem sie die Zeichen auf dem Band manipulierten. Dies gilt auch für andere mathematische Aktivitäten der Theoretischen Informatik, wie etwa Quantenprobabilistisches Rechnen. Die Funktion aus Churchs These wurde erst später mit einer Turing-Maschine belegt. Anfänglich stützten sie sich auf den λ-Kalkül.
Berechenbarkeit von Funktionen
Wenn natürliche Zahlen geeignet als Zeichenfolgen kodiert werden, wird eine Funktion auf natürlichen Zahlen als Turing-berechenbar bezeichnet, wenn die abstrakte Maschine den erforderlichen Algorithmus gefunden und diese Funktion auf Band gedruckt hat. Ein solches Gerät, das es in den 1930er Jahren noch nicht gab, würde in Zukunft als Computer gelten. Die abstrakte Turing-Maschine und Churchs These läuteten eine Ära der Entwicklung einRechengeräte. Es wurde bewiesen, dass die von beiden Wissenschaftlern formal definierten Klassen von Funktionen übereinstimmen. Daher wurden im Ergebnis beide Aussagen zu einer zusammengefasst. Rechenfunktionen und die These von Church hatten ebenfalls einen starken Einfluss auf das Konzept der Berechenbarkeit. Sie wurden auch zu einem wichtigen Werkzeug für die mathematische Logik und die Beweistheorie.
Begründung und Probleme der Methode
Es gibt widersprüchliche Ansichten über die These. Für die 1936 von Church und Turing aufgestellte „Arbeitshypothese“wurden zahlreiche Belege gesammelt. Aber alle bekannten Methoden oder Operationen zur Entdeckung neuer effektiv berechenbarer Funktionen aus gegebenen waren mit Methoden zum Bau von Maschinen verbunden, die damals noch nicht existierten. Um die Church-Turing-These zu beweisen, geht man davon aus, dass jedes realistische Berechnungsmodell äquivalent ist.
Aufgrund der Vielzahl unterschiedlicher Analysen gilt dies allgemein als besonders starker Beweis. Alle Versuche, den intuitiven Begriff einer effektiv berechenbaren Funktion genauer zu definieren, erwiesen sich als gleichwertig. Jede vorgeschlagene Analyse hat bewiesen, dass sie dieselbe Klasse von Funktionen herausgreift, nämlich diejenigen, die von Turing-Maschinen berechenbar sind. Einige Rechenmodelle erwiesen sich jedoch als effizienter in Bezug auf Zeit- und Speicherverbrauch für verschiedene Aufgaben. Später wurde festgestellt, dass die Grundkonzepte rekursiver Funktionen und Churchs These eher hypothetisch sind.
Thesis M
Es ist wichtig, zwischen Turings These und der Behauptung zu unterscheiden, dass alles, was von einem Rechengerät berechnet werden kann, auch von seiner Maschine berechnet werden kann. Die zweite Option hat eine eigene Definition. Gandhi nennt den zweiten Satz „Thesis M“. Es geht so: „Alles, was von einem Gerät berechnet werden kann, kann von einer Turing-Maschine berechnet werden.“Im engeren Sinn der These handelt es sich um einen empirischen Satz, dessen Wahrheitswert unbekannt ist. Turings These und „Thesis M“werden manchmal verwechselt. Die zweite Version ist im Großen und Ganzen falsch. Es wurden verschiedene bedingte Maschinen beschrieben, die Funktionen berechnen können, die nicht Turing-berechnet werden können. Es ist wichtig anzumerken, dass die erste These die zweite nicht beinh altet, aber mit ihrer Falschheit vereinbar ist.
Umgekehrte Implikation der These
In der Berechenbarkeitstheorie wird die These von Church als Beschreibung des Begriffs der Berechenbarkeit durch eine Klasse allgemeiner rekursiver Funktionen verwendet. Der Amerikaner Stephen Kleene hat eine allgemeinere Formulierung gegeben. Teilweise rekursiv nannte er alle durch Algorithmen berechenbaren Teilfunktionen.
Umgekehrte Implikation wird allgemein als umgekehrte These von Church bezeichnet. Sie liegt darin, dass jede rekursive Funktion positiver ganzer Zahlen effizient ausgewertet wird. Im engeren Sinne bezeichnet eine These lediglich eine solche Möglichkeit. Und im weiteren Sinne abstrahiert sie von der Frage, ob diese bedingte Maschine darin existieren kann.
Quantencomputer
Die Konzepte der berechenbaren Funktionen und die These von Church wurden zu einer wichtigen Entdeckung für die Mathematik, die Maschinentheorie und viele andere Wissenschaften. Aber die Technologie hat sich stark verändert und verbessert sich weiter. Es wird davon ausgegangen, dass Quantencomputer viele gängige Aufgaben in kürzerer Zeit erledigen können als moderne. Aber Fragen bleiben, wie das Stoppproblem. Ein Quantencomputer kann sie nicht beantworten. Und nach der Church-Turing-These auch kein anderes Rechengerät.
