Maschinenträume 2: KI und der Mythos der Hypercomputation
Inhalt
Wer unter Informatik – Computer Science – vor allem Binärsystem, Programmieren und Digitalisierung versteht, unterliegt einem verbreiteten Irrtum: Diese anspruchsvolle Ingenieurwissenschaft liegt im Spannungsfeld zwischen Mathematik (Theoretische Informatik), vielen Physik-Disziplinen (Technische Informatik) sowie Algorithmenentwicklung, Kognitionswissenschaften, Ergonomie und Wirtschaftswissenschaft (Praktische Informatik). Und dann steckt oft noch eine Menge echte Ingenieurskunst drin.
In der vorigen Folge hatte ich erwähnt, dass es im Nachdenken über Methoden des nachvollziehbaren, fehlerfreien Denkens wie Prädikatenlogik und Mathematik Anfang bis Mitte des 20. Jahrhunderts weitreichende – ja spektakuläre – Ergebnisse gab. Vieles davon gehört zu den essenziellen Werkzeugen der Theoretischen Informatik.
Ehe wir in das Thema einsteigen, schicke ich voraus: Da es sich um komplexe Materie handelt und dieser Artikel auch für Nicht-Informatiker verständlich sein soll, muss ich einiges drastisch vereinfachen. So gerne ich mit anderen Connaisseuren in der vollen Schönheit und Komplexität dieses Feldes schwelgen würde: In der Schulphysik wird auch noch die Newtonsche Gravitation gelehrt, obwohl wir sehr genau wissen, dass in Wirklichkeit die kompliziertere Relativitätstheorie gilt. Es ist eine drastische, aber sehr alltagstaugliche und didaktisch nützliche Vereinfachung.
Beginnen möchte ich mit einer kleinen Auswahl der Ergebnisse, die für die weitere Diskussion zentral sind: Da wäre zuerst der Gödelsche Unvollständigkeitssatz(öffnet im neuen Fenster) von 1931. Die wesentlichen Aussagen sind: Alle nicht-trivialen (hinreichend mächtigen) formalen Systeme enthalten Aussagen, die innerhalb dieses Systems weder bewiesen noch widerlegt werden können. Insbesondere ist die Widerspruchsfreiheit eines formalen Systems nicht innerhalb dieses Systems selbst beweisbar – dazu braucht es immer ein mächtigeres System. Wie wir noch sehen werden, resultieren daraus enge Grenzen für die KI – und wahrscheinlich auch für Erkenntnisse zu unserer eigenen Intelligenz.
In der Geschichte der Mathematik haben sich viele kluge Leute intensive Gedanken darüber gemacht, was eigentlich berechenbar, beweisbar und (im Sinne der Logik) entscheidbar ist. So entwickelte Church 1932-33 das λ-Kalkül und wies 1935-36 die Äquivalenz zu den 1933 von Gödel und Herbrand definierten µ-rekursiven Funktionen nach – eine wesentliche Grundlage der Berechenbarkeitstheorie, jenes Teilgebiet der Informatik, das sich mit der Frage befasst, was überhaupt berechenbar ist.
Turing wiederum entwickelte 1936 sein Konzept der Turing-Maschinen im Rahmen eines Beweises zur Nicht-Berechenbarkeit des Entscheidungsproblems. Turings Maschine ist so konzipiert, dass sie alles berechnen kann, was auch ein Mensch algorithmisch berechnen können würde. Daher wurde sie von ihm als Definition effektiv realisierbarer oder maschineller Berechenbarkeit vorgeschlagen.
Real konstruierbar und sehr anschaulich
Der besondere Charme von Turings Maschine war, dass sie real konstruierbar und sehr anschaulich war, ingenieurmäßig – alle anderen Ansätze waren hochabstrakte mathematische Konstruktionen. Eine Turing-Maschine besteht aus einem Schreib-/Lesekopf, der einen einfachen Automaten darstellt. Im Wesentlichen handelt es sich um eine endliche Tabelle, bei der die Zeilen dem inneren Zustand der Maschine entsprechen und die Spalten dem gerade eingelesenen Symbol.
Am Kreuzungspunkt von Zustand und Eingabe befindet sich die Aktion, die der Kopf als nächstes durchführt. Der Kopf liest also das Symbol seiner aktuellen Position auf einem Band und führt die seinem Zustand entsprechende Aktion aus, die – es gibt verschiedene gleichwertige Definitionen – darin bestehen kann, den Zustand zu wechseln, etwas auf das Band zu schreiben oder sich nach links oder rechts zu bewegen. Ist eine Turing-Maschine mit ihren Berechnungen fertig, hält sie an.
Man sagt, sie terminiert – und zwar nach endlich vielen Schritten oder Operationen. So etwas kann man prinzipiell tatsächlich bauen und frühe Computer waren auch gar nicht so weit weg von diesem Gedankenexperiment.
Der wirklich spannende und sehr überraschende Punkt ist aber, dass – wie Church, Kleene und Turing bewiesen – Turing-Maschine, λ-Kalkül und µ-Rekursion alle zueinander vollkommen äquivalent sind, also die identische Berechenbarkeit definieren. Man sagt, sie sind Turing-äquivalent, Turing-vollständig oder auch Turing-mächtig.
"Unendlich" bedeutet "ausreichend lang"
Noch erstaunlicher: Ich könnte hier jetzt seitenweise weitere Konzepte der Berechenbarkeit und verdienstvolle Namen auflisten – und alle irgendwie realisierbaren Berechenbarkeitskonzepte sind wieder Turing-äquivalent. Die Fülle Turing-äquivalenter Konzepte hat ihren Grund weniger im Versuch, über andere Formulierungen den Begriff und Bereich der Berechenbarkeit vielleicht doch noch zu erweitern – die Church-Turing-These galt schon früh als hochplausibel -, sondern vor allem darin, dass andere Konzepte der bessere Ausgangspunkt für bestimmte Überlegungen und Beweise sind. Ähnlich wie ein gut sortierter Werkzeugkasten verschiedene Bauformen von Schraubenschlüsseln derselben Größe vorhält, nutzt man auch in der Theorie das geeignetste, gleichwertige Instrument für die Arbeit – und das ist sehr häufig nicht die Turing-Maschine!
Es wird von manchen angeführt, dass die Turing-Maschine selbst nicht realistisch sei, weil ja ein unendliches Band vorausgesetzt wird. Tatsächlich hat aber jede terminierende Turing-Maschine, die also einen Algorithmus abgearbeitet hat, eben immer nur ein endliches Band benutzt. Der tatsächlich genutzte Speicher ist also immer endlich – so wie bei unseren Computern auch. Das "unendliche Band" ist also nur die mathematisch viel einfachere Formulierung für "ausreichend lang". Bei jedem konkreten Problem ist die benötigte Turing-Maschine in allen Aspekten endlich.
In diesem Sinne sind unsere Computer Turing-mächtig – auch Quanten-Computer (deren Vorteil ist komplexitätstheoretisch) -, wir müssen ihnen nur angemessen viel Speicher und Zeit für das konkrete Problem geben. Da für jeden existierenden Computer grundsätzlich gilt: "Die CPU ist zu lahm und der Speicher zu klein und die einzige Unbekannte ist, was zuerst schmerzt", bauen wir seit mehr als einem halben Jahrhundert immer schnellere Computer mit größeren Speichern. Tatsächlich sind unsere modernen und verteilten Computerarchitekturen sehr viel praktischer, praktikabler und effizienter, als Turing-Maschinen es sein könnten.
Auch alle modernen Programmiersprachen sind Turing-mächtig. Es kann darin also alles, was überhaupt berechenbar ist, auch als Algorithmus formuliert werden.
- Anzeige Hier geht es zu Künstliche Intelligenz: Wissensverarbeitung bei Amazon Wenn Sie auf diesen Link klicken und darüber einkaufen, erhält Golem eine kleine Provision. Dies ändert nichts am Preis der Artikel.