Zusammenfassung - Lösbarkeit des Halteproblems
Das Halteproblem - zu schwierig, um es mit einem Programm zu lösen
Jeder hat sie schon erlebt - Endlosschleifen, die das System blockieren. Da hilft dann nur noch "brutale Gewalt": (wenn möglich) den Prozess "killen" oder den Rechner ausschalten.
Kann man ein Programm schreiben, das andere Programme daraufhin untersucht, ob sie bei gegebenen Daten in eine Endlosschleife geraten oder nicht? Anders formuliert, kann man eine Software zur Lösung des Halteproblems entwickeln, um das meist frustrierende und manchmal sehr unangenehme Erleben von Endlosschleifen zu vermeiden?
In einer Computerzeitschrift hat einmal gestanden: „Geben Sie einem Computer die richtige Software, und er wird tun, was immer Sie wünschen. Die Maschine selbst mag Grenzen haben, doch für die Möglichkeiten von Software gibt es keine Grenzen.“
Schön wäre es! Es gibt Probleme in der Computerwelt, die so schwierig sind, dass sie die Grenzen des Computer-Machbaren sprengen. Das Halteproblem ist ein Beispiel für ein solches Problem. Es gibt bis jetzt keine Software, mit der man vorweg testen kann, ob ein Programm in eine Endlosschleife gerät, und es wird sie auch nie geben. Informatiker können nachweisen, dass sie nicht in der Lage sind, eine solche Software zu entwickeln. Es liegt dabei nicht am Unvermögen der Informatiker, sondern an den Grenzen der algorithmischen Problemlösemethode.
Diese Tatsache an sich ist auch etwas frustrierend. Aber gut, dass man darüber so genau Bescheid weiß!
Das Halteproblem
Wir fassen die bisher erzielten Ergebnisse hier noch einmal zusammen.
Das Halteproblem besteht darin, ein Programm (bzw. Algorithmus) zu entwickeln, mit dem man testen kann, ob ein übergebenes Programm bei der Verarbeitung übergebener Daten hält oder nicht.
Wir haben das Halteproblem speziell für die Programmiersprache Python untersucht und Programme in Form von Python-Funktionsdefinitionen betrachtet.
Dabei sind wir zu folgendem Ergebnis gekommen:
Satz (über die Lösbarkeit des Halteproblems in Python):
Man kann in Python keine Funktion entwickeln, die bei
Übergabe einer beliebigen Python-Funktionsdefinition und eines beliebigen Datentupels entscheidet, ob die betreffende
Funktion bei der Verarbeitung der Daten hält oder nicht. Das Halteproblem für Python-Programme ist demnach nicht mit einer
Python-Funktion entscheidbar.
Das Halteproblem ist damit nur für Python-Programme geklärt. Die folgenden Abschnitte sollen zeigen, wie man algorithmische Lösbarkeit von Problemen (wie z.B. dem Halteproblem) allgemein klärt.
