Alan Turing und die Macht des negativen Denkens

Algorithmen sind allgegenwärtig geworden. Sie optimieren unsere Arbeitswege, bearbeiten Zahlungen und koordinieren den Fluss des Internetverkehrs. Es scheint, dass es für jedes Problem, das in präzisen mathematischen Begriffen formuliert werden kann, einen Algorithmus gibt, der es lösen kann, zumindest in der Theorie.

Aber das ist nicht der Fall - einige scheinbar einfache Probleme können niemals algorithmisch gelöst werden. Der Pionier der Informatik, Alan Turing, bewies die Existenz solcher "unberechenbaren" Probleme vor fast einem Jahrhundert in demselben Aufsatz, in dem er das mathematische Modell der Berechnung formulierte, das die moderne Informatik begründete.

Turing bewies dieses bahnbrechende Ergebnis mit einer kontraintuitiven Strategie: Er definierte ein Problem, das einfach jeden Lösungsversuch ablehnt.

„Ich frage dich, was du tust, und dann sage ich: 'Nein, ich werde etwas anderes tun'“, sagte Rahul Ilango, ein Doktorand am Massachusetts Institute of Technology, der theoretische Informatik studiert.

Turings Strategie basierte auf einer mathematischen Technik namens Diagonalisierung, die eine illustre Geschichte hat. Hier ist eine vereinfachte Darstellung der Logik hinter seinem Beweis.

Stringtheorie

Die Diagonalisierung stammt von einem cleveren Trick zur Lösung eines alltäglichen Problems, das sich mit Zeichenfolgen von Bits befasst, von denen jedes entweder 0 oder 1 sein kann. Gegeben eine Liste solcher Zeichenfolgen, alle gleich lang, können Sie eine neue Zeichenfolge generieren, die nicht auf der Liste steht?

Die einfachste Strategie besteht darin, jede mögliche Zeichenfolge der Reihe nach zu betrachten. Nehmen wir an, Sie haben fünf Zeichenfolgen, von denen jede fünf Bits lang ist. Beginnen Sie damit, die Liste nach 00000 abzusuchen. Falls sie nicht vorhanden ist, können Sie aufhören; falls sie jedoch vorhanden ist, gehen Sie zu 00001 über und wiederholen Sie den Vorgang. Das ist einfach genug, aber es ist langsam für lange Listen langer Zeichenfolgen.

Diagonalisierung ist ein alternativer Ansatz, bei dem eine fehlende Zeichenfolge Bit für Bit aufgebaut wird. Beginnen Sie mit dem ersten Bit der ersten Zeichenfolge in der Liste und invertieren Sie es - das wird das erste Bit Ihrer neuen Zeichenfolge sein. Invertieren Sie dann das zweite Bit der zweiten Zeichenfolge und verwenden Sie es als das zweite Bit der neuen Zeichenfolge, und wiederholen Sie den Vorgang, bis Sie am Ende der Liste angekommen sind. Die invertierten Bits stellen sicher, dass sich die neue Zeichenfolge von jeder Zeichenfolge in der Originalliste an mindestens einer Stelle unterscheidet. (Sie bilden auch eine diagonale Linie durch die Liste der Zeichenfolgen, daher der Name der Technik.)

Für die Diagonalisierung muss nur ein Bit aus jeder Zeichenfolge auf der Liste betrachtet werden, weshalb sie oft viel schneller ist als andere Methoden. Aber ihre wahre Kraft liegt darin, wie gut sie mit Unendlichkeiten zusammenarbeitet.

"Die Zeichenfolgen können jetzt unendlich sein; die Liste kann unendlich sein - es funktioniert immer noch", sagte Ryan Williams, ein theoretischer Informatiker am MIT.

Die erste Person, die diese Kraft nutzte, war Georg Cantor, der Gründer der mathematischen Teildisziplin der Mengenlehre. Im Jahr 1873 nutzte Cantor die Diagonalisierung, um zu beweisen, dass manche Unendlichkeiten größer sind als andere. Sechs Jahrzehnte später adaptierte Turing Cantors Version der Diagonalisierung für die Theorie der Berechnung und gab ihr einen ausgesprochen unbeugsamen Charakter.

Das Limitationsspiel

Turing wollte die Existenz von mathematischen Problemen beweisen, die kein Algorithmus lösen kann - das heißt, Probleme mit wohldefinierten Eingaben und Ausgaben, aber ohne narrensicheres Verfahren, um von der Eingabe zur Ausgabe zu gelangen. Er machte diese vage Aufgabe etwas handhabbarer, indem er sich ausschließlich auf Entscheidungsprobleme konzentrierte, bei denen die Eingabe eine Zeichenfolge von 0s und 1s sein kann und die Ausgabe entweder 0 oder 1 ist.

Die Bestimmung, ob eine Zahl prim ist (nur durch 1 und sich selbst teilbar), ist ein Beispiel für ein Entscheidungsproblem - gegeben eine Zeichenfolge als Eingabe, die eine Zahl darstellt, ist die richtige Ausgabe 1, wenn die Zahl prim ist, und 0, wenn sie es nicht ist. Ein weiteres Beispiel ist die Überprüfung von Computerprogrammen auf Syntaxfehler (das Äquivalent zu grammatischen Fehlern). Dabei stellen Eingabezeichenfolgen den Code für verschiedene Programme dar - alle Programme können so dargestellt werden, da sie so auf Computern gespeichert und ausgeführt werden - und das Ziel besteht darin, 1 auszugeben, wenn der Code einen Syntaxfehler enthält, und 0, wenn er keinen enthält.

Ein Algorithmus löst ein Problem nur dann, wenn er für jede mögliche Eingabe die richtige Ausgabe liefert - wenn er auch nur einmal versagt, ist er kein allgemein verwendbarer Algorithmus für dieses Problem. In der Regel würden Sie zuerst das Problem, das Sie lösen möchten, spezifizieren und dann versuchen, einen Algorithmus zu finden, der es löst. Turing drehte diese Logik um, als er nach unlösbaren Problemen suchte - er stellte sich eine unendliche Liste aller möglichen Algorithmen vor und nutzte die Diagonalisierung, um ein stures Problem zu konstruieren, das jeden Algorithmus auf der Liste vereiteln würde.

Stellen Sie sich ein manipuliertes 20-Fragen-Spiel vor, bei dem der Antwortnde anstatt eines bestimmten Objekts eine Ausrede erfindet, um jede Frage zu verneinen. Am Ende des Spiels hat er ein Objekt beschrieben, das allein durch seine fehlenden Eigenschaften definiert ist.

Turings Diagonalisierungsbeweis ist eine Version dieses Spiels, bei dem die Fragen durch die unendliche Liste möglicher Algorithmen laufen und immer wieder fragen: "Kann dieser Algorithmus das Problem lösen, das wir als unberechenbar beweisen möchten?"

"Es ist so etwas wie 'unendlich viele Fragen'", sagte Williams.

Um das Spiel zu gewinnen, musste Turing ein Problem gestalten, bei dem die Antwort für jeden Algorithmus "nein" lautet. Das bedeutete, eine bestimmte Eingabe zu identifizieren, die den ersten Algorithmus dazu bringt, die falsche Ausgabe abzugeben, eine andere Eingabe, die den zweiten Algorithmus scheitern lässt, und so weiter. Er fand diese speziellen Eingaben mit einem Trick, der einem ähnelte, den Kurt Gödel vor Kurzem verwendet hatte, um zu beweisen, dass selbstreferenzielle Behauptungen wie "dieser Satz ist nicht beweisbar" den Grundlagen der Mathematik gefährlich werden.

Die entscheidende Erkenntnis war, dass jeder Algorithmus (oder jedes Programm) als eine Zeichenfolge von 0s und 1s dargestellt werden kann. Das bedeutet, dass ein Algorithmus, wie im Beispiel des Fehlerprüfungsprogramms, den Code eines anderen Algorithmus als Eingabe verwenden kann. In der Theorie kann ein Algorithmus sogar seinen eigenen Code als Eingabe verwenden.

Mit dieser Erkenntnis können wir ein Problem definieren, das nicht berechenbar ist, wie das in Turings Beweis: "Gegeben eine Eingabezeichenfolge, die den Code eines Algorithmus darstellt, geben Sie 1 aus, wenn dieser Algorithmus 0 ausgibt, wenn sein eigener Code die Eingabe ist; andernfalls geben Sie 0 aus." Jeder Algorithmus, der versucht, dieses Problem zu lösen, liefert mindestens einmal die falsche Ausgabe - nämlich die Eingabe, die seinem eigenen Code entspricht. Das bedeutet, dass dieses perverse Problem von keinem Algorithmus gelöst werden kann.

Was die Negation nicht erreichen kann

Informatiker hatten die Diagonalisierung noch nicht abgeschlossen. Im Jahr 1965 adaptierten Juris Hartmanis und Richard Stearns das Argument von Turing, um zu beweisen, dass nicht alle berechenbaren Probleme gleich sind - manche sind von Natur aus schwieriger als andere. Dieses Ergebnis gab den Anstoß für das Gebiet der Berechenbarkeitstheorie, das sich mit der Schwierigkeit von berechnenden Problemen befasst.

Aber die Komplexitätstheorie enthüllt auch die Grenzen von Turings gegenteiliger Methode. Im Jahr 1975 bewiesen Theodore Baker, John Gill und Robert Solovay, dass viele offene Fragen in der Komplexitätstheorie niemals allein durch Diagonalisierung gelöst werden können. Die berühmteste dieser Fragen ist das P vs. NP-Problem, das fragt, ob alle Probleme mit leicht überprüfbaren Lösungen auch mit dem richtigen genialen Algorithmus leicht zu lösen sind.

Die Blindstellen der Diagonalisierung sind eine direkte Folge des hohen Abstraktionsniveaus, das sie so mächtig macht. Turings Beweis beinhaltete kein unlösbares Problem, das in der Praxis auftreten könnte - stattdessen wurde ein solches Problem ad hoc konstruiert. Andere Beweise durch Diagonalisierung sind ebenfalls weit von der realen Welt entfernt und können deshalb Fragen nicht klären, bei denen Details aus der realen Welt eine Rolle spielen.

"Sie behandeln Berechnungen aus der Ferne", sagt Williams. "Ich stelle mir einen Mann vor, der mit Viren umgeht und sie durch eine spezielle Box anfasst."

Das Scheitern der Diagonalisierung war ein früher Hinweis darauf, dass die Lösung des P vs. NP-Problems ein langer Weg sein würde. Trotz ihrer Einschränkungen bleibt die Diagonalisierung jedoch eines der wichtigsten Werkzeuge im Arsenal der Komplexitätstheoretiker. Im Jahr 2011 benutzte Williams sie zusammen mit einer Vielzahl anderer Techniken, um zu beweisen, dass ein bestimmtes eingeschränktes Berechnungsmodell einige außergewöhnlich schwierige Probleme nicht lösen kann - ein Ergebnis, das den Forschern seit 25 Jahren entgangen war. Es war weit entfernt von der Lösung des P vs. NP-Problems, aber es stellte dennoch einen großen Fortschritt dar.

Wenn man beweisen will, dass etwas nicht möglich ist, sollte man die Kraft des einfachen Neinsagens nicht unterschätzen.

Quelle: Alan Turing and the Power of Negative Thinking | Quanta Magazine