Turings Diagonalisierungsbeweis ist eine Version dieses Spiels, bei der die Fragen die unendliche Liste möglicher Algorithmen durchlaufen und immer wieder fragen: „Kann dieser Algorithmus das Problem lösen, das wir als unberechenbar erweisen möchten?“
„Es sind sozusagen ‚Unendlichkeitsfragen‘“, sagte Williams.
Um das Spiel zu gewinnen, musste Turing ein Problem entwickeln, bei dem die Antwort für jeden Algorithmus „Nein“ lautet. Das bedeutete, eine bestimmte Eingabe zu identifizieren, die dazu führt, dass der erste Algorithmus eine falsche Antwort ausgibt, eine andere Eingabe, die dazu führt, dass der zweite fehlschlägt, und so weiter. Er fand diese speziellen Eingaben mit einem Trick, der dem ähnelte, den Kurt Gödel kürzlich angewendet hatte beweisen dass selbstreferenzielle Behauptungen wie „Diese Aussage ist unbeweisbar“ Probleme für die Grundlagen der Mathematik bedeuteten.
Die wichtigste Erkenntnis war, dass jeder Algorithmus (oder jedes Programm) als eine Folge von Nullen und Einsen dargestellt werden kann. Das bedeutet, wie im Beispiel des Fehlerprüfprogramms, dass ein Algorithmus den Code eines anderen Algorithmus als Eingabe nehmen kann. Im Prinzip kann ein Algorithmus sogar seinen eigenen Code als Eingabe verwenden.
Mit dieser Einsicht können wir ein unberechenbares Problem wie das in Turings Beweis definieren: „Gegebene Eingabezeichenfolge, die den Code eines Algorithmus darstellt, Ausgabe 1, wenn dieser Algorithmus 0 ausgibt, wenn sein eigener Code die Eingabe ist; andernfalls Ausgabe 0.“ Jeder Algorithmus, der versucht, dieses Problem zu lösen, erzeugt bei mindestens einer Eingabe die falsche Ausgabe – nämlich der Eingabe, die seinem eigenen Code entspricht. Das bedeutet, dass dieses perverse Problem durch keinen Algorithmus gelöst werden kann.
Was Negation nicht kann
Informatiker waren mit der Diagonalisierung noch nicht fertig. Im Jahr 1965 passten Juris Hartmanis und Richard Stearns Turings Argumentation an beweisen dass nicht alle berechenbaren Probleme gleich sind – einige sind von Natur aus schwieriger als andere. Dieses Ergebnis begründete das Gebiet der Computational Complexity Theory, das die Schwierigkeit von Rechenproblemen untersucht.
Die Komplexitätstheorie zeigte aber auch die Grenzen der gegenteiligen Methode von Turing auf. 1975 Theodore Baker, John Gill und Robert Solovay bewiesen dass viele offene Fragen der Komplexitätstheorie niemals allein durch Diagonalisierung gelöst werden können. Das wichtigste davon ist das berühmte P-NP-Problem, bei dem gefragt wird, ob alle Probleme mit leicht überprüfbaren Lösungen auch mit dem richtigen ausgeklügelten Algorithmus leicht zu lösen sind.
Die blinden Flecken der Diagonalisierung sind eine direkte Folge des hohen Abstraktionsniveaus, das sie so mächtig macht. Turings Beweis beinhaltete kein unberechenbares Problem, das in der Praxis auftreten könnte – stattdessen wurde ein solches Problem spontan erfunden. Andere Diagonalisierungsbeweise sind ähnlich weit von der realen Welt entfernt und können daher keine Fragen lösen, bei denen es auf reale Details ankommt.
„Sie führen Berechnungen aus der Ferne durch“, sagte Williams. „Ich stelle mir einen Mann vor, der sich mit Viren befasst und über ein Handschuhfach darauf zugreift.“
Das Scheitern der Diagonalisierung war ein früher Hinweis darauf, dass das P-NP-Problem gelöst werden würde eine lange Reise. Doch trotz ihrer Einschränkungen bleibt die Diagonalisierung eines der wichtigsten Werkzeuge im Arsenal der Komplexitätstheoretiker. Im Jahr 2011 nutzte Williams es zusammen mit einer Reihe anderer Techniken, um beweisen dass ein bestimmtes eingeschränktes Rechenmodell einige außerordentlich schwierige Probleme nicht lösen konnte – ein Ergebnis, das den Forschern 25 Jahre lang entgangen war. Von einer Lösung zwischen P und NP war es weit entfernt, aber es stellte dennoch einen großen Fortschritt dar.
Wenn Sie beweisen wollen, dass etwas nicht möglich ist, unterschätzen Sie nicht die Macht, einfach Nein zu sagen.
Originelle Geschichte Nachdruck mit Genehmigung von Quanta-Magazin, eine redaktionell unabhängige Veröffentlichung der Simons-Stiftung Deren Aufgabe ist es, das öffentliche Verständnis der Wissenschaft zu verbessern, indem sie Forschungsentwicklungen und -trends in der Mathematik sowie den Physik- und Biowissenschaften abdeckt.