Algorithmische Lösbarkeit von Problemen

Lösbarkeit von Problemen

Der Nachweis, dass ein Problem lösbar ist, wird meist durch Angabe einer Lösung erbracht.

Viel schwieriger ist es in der Regel nachzuweisen, dass ein Problem unlösbar ist. Man muss dann Aussagen über alle denkbaren Problemlösemöglichkeiten machen, also sowohl über die, die man schon erprobt hat, als auch über die, an die man noch gar nicht gedacht hat.

Ein sicheres Fundament erhalten Unlösbarkeitsnachweise, wenn die zur Lösung einsetzbaren Mittel präzisiert werden. Im Fall des Neun-Punkte-Problems wurde hierzu zunächst der Begriff "gitterbasierter Streckenzug" geklärt. Mit Hilfe dieses Begriffes konnte dann die Unlösbarkeit bzgl. der vorgenommenen Präzisierung begründet werden.

Ähnlich verhält es sich auch in der Informatik. Hier ist man an der algorithmischen Lösbarkeit von Problemen interessiert.

Im Abschnitt Zusammenfassung - Lösbarkeit des Halteproblems. haben wir gesehen, dass das Halteproblem mit den Mitteln von Python nicht lösbar ist. Ist es damit aber auch algorithmisch unslösbar? Wie die Betrachtungen zum Neun-Punkte-Problem zeigen, sollte man eher vorsichtig sein. Über unkonventionelle Wege könnte es ja durchaus möglich sein, das Halteproblem algorithmisch zu lösen

Die einzige Möglichkeit, um zu einem befriedigenden und nicht auf Spekulation basierenden Ergebnis zu gelangen, besteht darin, die Mittel beim algorithmischen Problemlösen zu präzisieren. Wir schlagen also einen Weg ein, den wir analog auch beim Neun-Punkte-Problem gegangen sind.

Schwierigkeiten bei der Präzisierung der algorithmischen Methode

Was ist alles erlaubt beim algorithmischen Problemlösen? Eine Präzisierung des Algorithmusbegriffs liefert eine erste Antwort.

Ein Algorithmus ist eine Verarbeitungsvorschrift, die so präzise formuliert ist, dass sie auch von einer Maschine abgearbeitet werden kann.

Oft ist es gar nicht so einfach zu entscheiden, ob eine Verfahrensbeschreibung als Algorithmus bezeichnet werden kann oder nicht. Die folgenden Kriterien liefern eine Orientierung:

• Eindeutigkeit, d. h. die einzelnen Schritte und ihre Abfolge sind unmissverständlich beschrieben
• Ausführbarkeit, d. h. der Prozessor muss die Einzelschritte ausführen können
• Allgemeinheit, d. h. es wird nicht nur ein Problem, sondern eine ganze Klasse von Problemen gelöst
• Endlichkeit, d. h. seine Beschreibung besteht aus einem Text endlicher Länge

Mit Prozessor wird hier die Maschine, Person oder auch gedachte Einheit verstanden, die den Algorithmus ausführen soll. Die Ausführbarkeit eines Algorithmus hängt so von den Möglichkeiten des Prozessors ab.

Sind damit alle Unklarheiten beseitigt? Eher nicht, denn was heißt "Ausführbarkeit" bzw. was sind die "Möglichkeiten des Prozessors".

Das folgende Beispiel soll dies verdeutlichen.

Eingabe: Polynomgleichung p mit ganzzahligen Koeffizienten, 
         in der verschiedene Variablen 
         mit verschiedenen Exponenten vorkommen können 
         z.B.: x3 + 5x2y2z – xz + 37 = 0
WENN p ganzzahlige Lösungen hat:
    weise allen Variablen den Wert 0 zu
    SOLANGE noch keine Lösung gefunden wurde:
        verändere systematisch die Werte der Variablen
    Ausgabe: Lösungstupel
SONST:
    Ausgabe: "Es gibt keine Lösungen."

Handelt es sich bei der vorliegenden Beschreibung um einen Algorithmus? Was spricht dafür, was spricht dagegen?

Unklar ist z.B., ob eine Bedingung wie "p hat ganzzahlige Lösungen" ausführbar ist. Kann der - oben nicht näher beschriebene - "Prozessor" eine solche Bedingung überhaupt überprüfen? An diesem einfachen Beispiel sieht man bereits, wie wenig aussagekräftig das oben formulierte Kriterium der Ausführbarkeit ist.

Ziel ist es im Folgenden, diese Lücke zu schließen und den Algorithmusbegriff formal zu definieren. Mit einem solchermaßen präzisierten Algorithmusbegriff kann dann die algorithmische Lösbarkeit von Problemen argumentativ geklärt werden.