Neulich habe ich mit einem Freund Schach gespielt, und wir sprachen über den unglaublichen Sieg des IBM-Computers Deep Blue gegen den Weltmeister in den 90er-Jahren. Damals bedeutete der Sieg einen enormen Fortschritt für die Informatik. Als rechnerisches Problem betrachtet war Schach jedoch leicht – da es für jeden Zug eine berechenbare Lösung gibt. Die Herausforderung in dieser Zeit war es also, alle Möglichkeiten für Spielzüge in praktikabler Zeit zu berechnen.
Was bedeutet eigentlich Entscheidbarkeit?
In unserem Fachgebiet bezeichnen wir diese Art von lösbaren Problemen als «entscheidbar». Viele Probleme in der Informatik sind jedoch nicht entscheidbar, was bedeutet, dass es auch in Zukunft kein Computerprogramm auf der Welt geben wird, das immer eine richtige Antwort berechnet. Unentscheidbarkeit führt zu falschen Antworten oder dazu, dass das Programm endlos läuft, ohne eine Antwort zu liefern – das Resultat ist ein Systemabsturz.
Kann man aber nicht einen intelligenten Qualitätssicherungs-Algorithmus schreiben, der prüft, ob ein Programm absturzgefährdet ist oder nicht? Diese Frage ist wichtiger, als sie erscheint. Denken Sie an ein komplexes System wie ein Flugzeug-Leitsystem. In diesem Fall kann ein Softwarefehler katastrophale Folgen haben. Also, werden wir jemals das ultimative automatische Prüfprogramm für all unsere Software haben, um zu wissen, ob sie entscheidbar ist oder nicht?
Es gibt kein universelles Programm
Leider heisst die Antwort nein, wie der Vater der Informatik, Alan Turing, bereits 1936 bewiesen hat. Der Grund ist das «Halting Problem»: Wenn ein Computerprogramm eine klare Aufgabe hat – wird es diese dann immer beenden, oder wird es sich manchmal in einer Endlosschleife aufhängen? Turing hat bewiesen, dass es kein universelles Programm geben kann, das diese Frage für alle möglichen Eingaben beantwortet. Für den Beweis nutzt er den Widerspruch aus unserer Problemstellung. Mit anderen Worten: Ein Stück Software zu schreiben, um Software zu analysieren, das geht nicht immer.
Wenn man darüber nachdenkt, stösst man auch in der Alltagssprache auf solche selbstreferenziellen Probleme. Nehmen wir zum Beispiel den Satz «Dieser Satz ist falsch». Das ist ein klassisches Paradoxon: Wenn der Satz falsch ist, dann ist der Satz wahr – und umgekehrt. Aber da der Satz grammatikalisch korrekt ist, gibt es keine einfache Lösung für diese Pattsituation, ausser einzugestehen, dass, wenn Sätze über sich selbst sprechen, manchmal die Aussagekraft nicht gewährleistet ist. Turing zeigte, dass das Gleiche für Computerprogramme gilt – wobei in diesem Fall das Argument sehr präzise mathematisch geführt werden kann.
Macht Computer auch Fehler?
Zum Glück ist dieser Unmöglichkeitsnachweis in erster Linie theoretisch, und in der Praxis verfügen wir über Werkzeuge, die die Arbeit der Softwareentwickler erheblich erleichtern. Dennoch: Die grundlegende Lektion ist die der Unzulänglichkeit. Egal, wie clever wir sind, wir sollten nicht vergessen: Wir können nie ganz sicher sein, dass sich nicht ein kleiner Fehler in unsere immer intelligenteren Computer eingeschlichen hat.
