Gibt es Probleme, die Computer nicht lösen können?

Information, Unterhaltung, Arbeit, Bildung, schnelle Lösungen für komplexe Probleme ... Im Allgemeinen haben wir eine ziemlich solide Vorstellung davon, was wir bei der Nutzung eines Computers wollen. Tatsächlich gibt es Momente, in denen ein System scheinbar alles lösen kann, und das führt uns zu einer sehr interessanten logischen Übung: Stellen Sie sich einen Computer mit unendlicher Zeit, Energie und Rechenleistung vor. Gibt es also etwas, das er trotz dieser Vorteile nicht lösen kann? Die kurze Antwort lautet „ja“, aber wir brauchen die Hilfe von Tom Scott für den Rest ...

Wie oft ist das schon passiert? Eine einfache Frage wirft uns in ein schwarzes Loch aus Logik und Vernunft. Der Mathematiker David Hilbert (derselbe, der das unendliche Hotel erfunden hat) geriet 1928 zusammen mit seinem Kollegen Wilhelm Ackermann in diese Lage, als beide die Herausforderung des Entscheidungsproblems oder des „Problems der Entscheidung“ vorstellten. In äußerst lockeren Worten schlägt das Problem Folgendes vor: Ist es möglich zu bestimmen, ob eine gegebene Aussage beweisbar ist oder nicht? Mit genügend Zeit und Energie – können wir die Antwort auf alles finden?

Was hat das nun mit Computern zu tun? Eigentlich lässt sich diese Frage von Hilbert auf sehr besondere Weise auf die Welt der Informatik übertragen: Stellen Sie sich den Code eines Programms vor – irgendein Programm. Ist es möglich, diesen Code zu analysieren und automatisch zu bestimmen, ob er anhalten oder in eine Endlosschleife geraten wird? An diesem Punkt schlägt jemand ein Beispiel vor wie:

10 PRINT “HOLA MUNDO”
20 GOTO 10
RUN

Natürlich führt dieses Stück Code zu einer Endlosschleife ... aber der Unterschied ist, dass es so entworfen wurde. Zu bestimmen, ob einige Programme anhalten oder für immer weiterlaufen, das ist einfach. Die Idee, irgendeinen Code – alle Codes – zu nehmen und zu analysieren, um endgültig festzustellen, ob sie beenden oder in eine Schleife geraten, mag an der Oberfläche einfach erscheinen, ist aber mathematisch unmöglich. Woher wissen wir das? Dank eines gewissen Herrn namens Alan Turing und der berühmten Maschine, die seinen Namen trägt, aus dem Jahr 1936.

Hier rettet uns Tom Scott mit seiner Erklärung: Stellen wir uns ein Programm namens „Halts“ vor, das eine Probe von irgendeinem Code sehen und bestimmen kann, ob es anhalten wird (wir müssen nicht wissen, wie es das macht, wichtig ist, dass es funktioniert). Noch einmal: „Halts“ sieht den Code und antwortet „Ja“ (es hält an) oder „Nein“ (Endlosschleife). Nun visualisieren wir ein zweites Programm, das mit „Halts“ verbunden ist und genau das Gegenteil seiner Antwort tut. Das heißt: wenn „Halts“ sagt, dass der Code anhält, gerät das zweite Programm in eine Endlosschleife, und wenn es sagt, dass es in eine Schleife gerät, hält es an.

Dieses System wird „Gegenteil“ genannt, weil es im Wesentlichen das Gegenteil von dem tut, was man hineingibt ... aber hier bricht Turing mit seinem Vorschlag alles: den vollständigen Code, der „Gegenteil“ ausmacht, zu nehmen und sich selbst zu analysieren. Das Ergebnis ... ist, dass es kein Ergebnis gibt. Es ist ein Paradoxon, eine mathematische Unmöglichkeit. Selbst mit den idealen Anfangsbedingungen bringt eine minimale Variation den Prozess zum Kollabieren. Und da haben wir unsere Antwort auf die ursprüngliche Frage: Es gibt mindestens eine Sache, die Computer nicht und nie lösen können.