Meine Lieblingsautoren (David Deutsch, Roger Penrose und Douglas Hofstadter) befassen sich alle mit der Church-Turing-These der Computertheorie und, was noch wichtiger ist, ihrer stärksten Interpretation: Dem Turing-Prinzip. In diesem Beitrag werde ich zuerst die Church-Turing-These in Laienbegriffen erklären.
Als ich an meinem Informatikstudium arbeitete, studierte ich Turing-Maschinen und die Church-Turing-These in meinem Intro to Computational Theory-Kurs. Damals dachte ich, es sei eine große Zeitverschwendung. Ich wollte nur Computer programmieren und ich konnte mich nicht weniger um diesen längst verstorbenen Turing-Typen (noch um diesen Kirchenmann) noch um seine dummen theoretischen Maschinen kümmern.
Jetzt, da ich die philosophischen Auswirkungen der Church-Turing-These verstehe, wünschte ich, ich hätte im Unterricht darauf geachtet! Weil die Church-Turing-These, wenn sie wahr ist, einige tiefgreifende philosophische Auswirkungen hat und uns auch etwas über die Tiefe — und besondere — Natur der Realität erzählen könnte.
Endliche Automaten
Alle Texte und Klassen zur Theorie der Berechnung beginnen mit etwas, das „Endliche Automaten“ genannt wird.“ Die Grundidee dahinter ist ziemlich einfach. Man stelle sich nur eine einfache ‚Maschine‘ vor, die in der Lage ist, Entscheidungen zu treffen und sich zwischen Zuständen zu bewegen. Hier ist ein Beispiel für ein sehr einfaches, das die „Logik“ eines Münz-Drehkreuzes darstellt.
Im Klartext, das heißt, wenn Sie versuchen, durch ein Drehkreuz zu schieben, die gesperrt ist, können Sie nicht, wenn Sie nicht zuerst in einer Münze setzen. Wenn Sie eine Münze eingelegt, aber noch nicht durchgedrückt haben, lassen Sie zusätzliche Münzen einfach in einem entsperrten Zustand. Wenn Sie in einer Münze setzen, dann können Sie durchdrücken. Es sperrt dann wieder für die nächste Person.
Es war wahrscheinlich aus dem Diagramm leichter zu verstehen als aus der Beschreibung.
Endliche Automaten sind in der Lage, weitaus kompliziertere Logik auszuführen. Dies sollte Ihnen jedoch ein grundlegendes Gefühl dafür geben, wie endliche Automaten funktionieren.
Eine Sache zu beachten ist, dass ein endlicher Automat, wie der obige, rein theoretisch ist, weil er nur als ein Bündel von Blasen und Linien auf einem Blatt Papier existiert. Es ist nicht so, als gäbe es eine kleine „endliche Automatenmaschine“ im Drehkreuz, die diese Entscheidungen trifft. Oder vielleicht sollte ich stattdessen sagen, dass das Drehkreuz selbst die endliche Automatenmaschine ist.
Wenn wir wirklich wollten, könnten wir wahrscheinlich eine Maschine im wirklichen Leben bauen, die ein endlicher Automat wäre.Es gibt nichts, was jemanden davon abhält, es als echte Maschine im wirklichen Leben zu bauen und es dann in das Drehkreuz zu installieren. Das ist einfach nicht der billigste Weg, es zu tun.
Jedes „Programm“, das Sie als Zeichnung eines endlichen Automaten erstellen, kann also in eine echte „Berechnung“ umgewandelt werden, die wirklich funktioniert. Die Bedeutung des Unterschieds zwischen einer Rechenmaschine, die tatsächlich existieren kann (wie ein endlicher Automat), und einer, die nur hypothetisch ist und gegen die Gesetze der Physik verstößt, wird in einem Moment wichtig.
Leistungsstärkere Maschinen
Mit fortschreitender Klasse in der Computertheorie werden die Schüler in immer komplexere Maschinen eingeführt, die leistungsfähiger sind als endliche Automaten. Wie die Abbildung rechts zeigt, ist der Pushdown Automata (PDA) der nächststärkste. Ein PDA ist eigentlich nur ein DFA mit einer Art „Speicher“. Dieser Speicher ermöglicht es einem PDA, Berechnungen (oder Programme) zu erstellen und auszuführen, die ein DFA nicht kann.
Der entscheidende Punkt ist nur, dass es bestimmte Arten von Programmen gibt, die für einen PDA geschrieben werden können, die nicht auf einem deterministischen endlichen Automaten (DFA) geschrieben werden können. Mit anderen Worten, PDAs sind „leistungsfähiger“ als DFAs, weil sie Klassen von „Programmen“ ausdrücken können, die DFAs nicht können.
Es gibt also eine Beziehung zwischen DFAs und PDAs in Bezug auf „Rechenleistung“.“ Es ist nämlich möglich zu beweisen, dass jedes auf einem DFA geschriebene Programm auch auf einem PDA geschrieben werden kann, aber dass das Gegenteil nicht der Fall ist.
Der Beweis liegt im Beweis
Der Beweis, dass ein PDA alles ausführen kann, was ein DFA kann, wird durch ein Schema erbracht, mit dem die Logik eines DFA einem PDA zugeordnet werden kann. Da ein PDA nur ein DFA mit Speicher ist, ist dies nicht schwer zu tun — verwenden Sie einfach nicht die „Speicherfunktion“.
Aber was ist mit dem Gegenteil? Können wir beweisen, dass es unmöglich ist, bestimmte Arten von „Programmen“, die für einen PDA geschrieben wurden, in einen DFA zu übersetzen? Das heißt, gibt es einen Beweis dafür, dass Pushdown-Automaten nicht auf endliche Automaten abgebildet werden können? Oder gehen wir nur davon aus, dass ein endlicher Automat weniger leistungsfähig ist als ein Pushdown-Automat, weil wir derzeit keine Möglichkeit kennen, einen PDA einer FDA zuzuordnen? Vielleicht gibt es eine Möglichkeit, PDAs FDAs zuzuordnen, und vielleicht hat noch niemand herausgefunden, wie das geht? Ist das nicht zumindest eine Möglichkeit?
Wie sich herausstellt, ist es möglich zu beweisen, dass ein PDA bestimmte Arten von Programmen ausführen kann, die ein DFA nicht ausführen kann. Die Art und Weise, wie Sie es tun würden, ist, dass Sie eine Berechnung finden würden (dh. b. ein Programm), das Sie nachweisen können, dass ein DFA nicht berechnen kann, und dann nachweisen, dass ein PDA es berechnen kann.
Rechenleistung einer Maschine
Diese Tatsache — dass es leistungsstärkere (PDA) und weniger leistungsfähige (DFA) Logikmaschinen gibt — ist an und für sich interessant.
Aber es führt zu einer philosophischen Frage: Gibt es so etwas wie eine „mächtigste Rechenmaschine?“
Wenn es eine solche „mächtigste Maschine“gäbe, woher würden wir wissen, dass eine bestimmte vorgeschlagene Maschine „die mächtigste“ist?“ Oder gibt es nur verschiedene Arten von Rechenmaschinen und Sie müssen die richtige für den Job auswählen?
Turing-Maschinen
Welche Maschine ist also leistungsfähiger als ein PDA?
Wie es die Geschichte so will, wurden ungefähr zur gleichen Zeit zwei sehr unterschiedliche Arten von „Maschinen“ vorgeschlagen, die beide nachweislich leistungsfähiger waren als PDAs.
Eine davon war Alan Turings Turing-Maschine. Die andere war nicht so sehr eine Maschine, sondern eine clevere Reihe von Notationen, die von Alonzo Church entwickelt wurden und dem gleichen Zweck dienten wie die Entwicklung einer Maschine. Von diesen beiden „Maschinen“ ist die Turing-Maschine konzeptionell einfacher zu unterrichten, daher ist dies normalerweise die Maschine, die in einem Computertheoriekurs unterrichtet wird.
Turing-Maschinen sind lustige kleine theoretische Maschinen, die einen Lese- / Schreibkopf und ein (hypothetisches) Papierband haben, von dem sie lesen oder auf das sie schreiben können. Basierend auf dem, was die Turing-Maschine liest, versetzt sie die Turing-Maschine in einen Aktionszustand, der eine Art Kombination von Aufgaben ausführt, die entweder darin bestehen, den Lese- / Schreibkopf vorwärts oder rückwärts zu bewegen, von einer neuen Position auf dem Band zu lesen oder zu schreiben von einer neuen Position auf dem Band. Eine Turing-Maschine sieht so aus:
Turing-Maschinen und moderne Computer
Interessant ist, dass eine Turing-Maschine trotz ihres oberflächlichen Erscheinungsbildes einem modernen Computer ziemlich ähnlich ist. In einem modernen Computer entspricht die Zentraleinheit (CPU) dem Schreib- / Lesekopf einer Turing-Maschine. Die Speicherchips (RAM oder ROM) sind den Zellen des langen Papierbandes sehr ähnlich, von denen die Drehmaschine lesen oder schreiben kann. Moderne Computer scheinen also in etwa einer Turing-Maschine zu entsprechen.
Ein moderner Computer hat einen Vorteil gegenüber der Turing-Maschine. Ein moderner Computer muss sich nicht wie eine Turing-Maschine sequentiell von einer Zelle seines „Speichers“ bewegen.
Die Tatsache, dass eine Turing-Maschine jeweils nur eine Zelle bewegen kann, scheint eine erhebliche Einschränkung zu sein, nicht wahr? Wir haben gerade gesehen, wie einige Maschinen logisch leistungsfähiger sind als andere: Ein PDA kann Rechenaufgaben ausführen, die eine FDA nicht ausführen kann. Vielleicht gibt es also Maschinen, die leistungsfähiger sind als Turing-Maschinen, die Aufgaben ausführen können, die Turing-Maschinen nicht können? Und vielleicht können moderne Computer — aufgrund ihrer Fähigkeit, im Speicher herumzuspringen, anstatt sich nacheinander von Zelle zu Zelle bewegen zu müssen – einige Programme ausführen, die eine Turing-Maschine nicht kann?
In der Tat haben moderne Computer tatsächlich weniger Ausdruckskraft als eine Turing-Maschine aufgrund der Tatsache, dass Turing-Maschinen so konzipiert wurden, dass sie ein unendlich langes Papierband (dh unendliches Gedächtnis) haben, wo ein realer Computer immer endliches Gedächtnis haben wird. Im Allgemeinen macht dies jedoch kaum einen Unterschied darin, welche Arten von Berechnungen man durchführen kann, da Menschen im Allgemeinen nicht so sehr an unendlich langen Berechnungen interessiert sind, die unendlich lange Ergebnisse liefern. Deshalb sage ich, dass moderne Computer und Turing-Maschinen „ungefähr“ gleichwertig sind. In der Tat, solange Sie eine beliebige, aber endliche Größe des Speichers annehmen, sind sie genau gleichwertig in Bezug darauf, welche Arten von Programmen sie ausführen können.
Die Turing-These der Kirche: Turing-Maschine = maximale logische Leistung
Aber was ist mit der armen Alonzo-Kirche? Seine arme kleine „Maschine“ vergessen, weil Turing-Maschinen sind leichter zu lehren. Ist seine Maschine vielleicht in der Lage, einige Berechnungen / Programme auszudrücken, die eine Turing-Maschine nicht kann, oder umgekehrt?
Wäre es nicht ein stellarer Zufall, wenn Alan Turing und Alonzo Church zufällig zwei völlig unterschiedliche Arten theoretischer Rechenmaschinen geschaffen hätten und sie genau identisch wären in Bezug darauf, welche Arten von Berechnungen sie durchführen könnten?
Stellen Sie sich also die Überraschung aller vor, als Alan Turing einen Beweis erbringen konnte, dass jedes für eine Turing-Maschine geschriebene Programm auch für eine Kirchenmaschine geschrieben werden kann, und auch einen Beweis, dass jedes für eine Kirchenmaschine geschriebene Programm auch für eine Turing-Maschine geschrieben werden kann.
In der Tat gibt es eine Reihe von vorgeschlagenen Arten von theoretischen Rechenmaschinen. Zum Beispiel versuchten Theoretiker, einer Turing-Maschine zu erlauben, mehrere Bänder zum Lesen / Schreiben zu haben. Sie versuchten sogar, einer Turing-Maschine ein 2-dimensionales Blatt zum Lesen und Schreiben zu ermöglichen. Theoretiker versuchten alle möglichen Verbesserungen an Turing-Maschinen (und Kirchenmaschinen).
Und bisher war es möglich, für jeden einzelnen von ihnen einen Beweis zu erbringen, dass sie einer einfachen Turingmaschine entsprechen.
Das scheint ein wilder Zufall zu sein, nicht wahr? Und es wäre ein wilder Zufall, es sei denn, es gibt eine Obergrenze dafür, welche Arten von Berechnungen durchgeführt werden können.
Wenn es eine solche obere Grenze gibt, dann wäre es kein Zufall, dass die Turing-Maschine und die Church-Maschine und alle anderen vorgeschlagenen Rechenmaschinen alle zufällig die gleiche Rechenleistung haben, da der Grund, warum sie alle äquivalent sind, darin besteht, dass wir die obere Grenze der Rechenleistung erreicht haben.
Aber können wir beweisen, dass es da draußen keine Rechenmaschine gibt — eine, die wir noch nicht entdeckt haben —, die die Fähigkeit hat, Berechnungen durchzuführen, die eine Turing-Maschine nicht kann?
Wie genau würden wir einen solchen Beweis erbringen? Tatsache ist, dass wir nicht beweisen können, dass es nichts Mächtigeres als eine Turing-Maschine gibt. Also, wer weiß, vielleicht gibt es.
Aber Tatsache ist, dass wir keine solchen Maschinen finden (oder erfinden) können.
Nach beträchtlichen Bemühungen, einen Weg zu finden, die Leistung von Turing-Maschinen zu verbessern, wurde schließlich die Church-Turing-These akzeptiert, obwohl sie sich nicht als wahr erwies. Die Church-Turing-These sagt im Wesentlichen so etwas:
Es ist nicht möglich, irgendeine Art von Rechenmaschine zu entwickeln, die ein Logikprogramm ausführen kann, das eine einfache alte Turing-Maschine nicht kann.
Oder in anderen Worten:
Turing-Maschinen und ihre Äquivalente sind die leistungsfähigsten möglichen Arten von Rechenmaschinen, und es gibt keine leistungsfähigeren, von denen wir noch nichts wissen.
Nach jahrelanger Forschung an dieser These gilt diese These im Grunde immer noch. Wir werden später sehen, dass es mit der Einführung theoretischer Quantencomputer eine gewisse Modifikation der These gegeben hat. Aber im Grunde gilt die These auch heute noch. Niemand hat jemals einen Weg gefunden, Turing-Maschinen in Bezug auf logische Ausdruckskraft zu übertreffen. Turing-Maschinen sind immer noch der amtierende Champion.
Jetzt verstehst du also die Church-Turing-These. Die Church-Turing-These entspricht jedoch nicht ganz dem Turing-Prinzip. Also werde ich in einem zukünftigen Beitrag entwickeln, was der Unterschied ist und was seine philosophischen Auswirkungen sind.
Anmerkungen
Das Turing-Prinzip. So benannt von Roger Penrose, der nicht daran glaubt (zumindest nicht in der jetzigen Form). Es wurde von David Deutsch zum Turing-Deutsch-Prinzip entwickelt, der zumindest in seiner Form daran glaubt.) (Siehe Artikel in Wikipedia für weitere Details)