Während meiner Auszeit erscheinen hier einige Gastbeiträge von anderen Bloggern. Wenn ihr auch Lust habt, euer Blog (euren Podcast, euer Videoblog, etc) hier vorzustellen oder einfach nur mal einen Artikel schreiben wollt, dann macht mit!
Heute gibt es einen Artikel von Moritz Moxter, Autor des Blogs 7tupel.net.
Als Informatiker möchte ich mir heute die Zeit nehmen darauf einzugehen was aus Sicht des Informatikers ein Problem ist. Dabei geht es nicht um ein bestimmtes Problem, sondern um die generelle Frage nach allen Problemen.
Die Informatik ist eine Wissenschaft die sich in erste Linie damit beschäftigt Probleme zu analysieren und – wenn möglich – zu lösen. Es geht anders als die meisten Menschen zunächst vermuten nicht um Computer. Der Computer ist vielmehr ein Hilfsmittel, vergleichbar mit dem Teleskop in der Astronomie: Hier geht es schließlich auch nicht um Teleskope, diese sind bloß ein Hilfsmittel. Probleme können sehr unterschiedlich sein. Einige davon begenen uns jeden Tag, zu den bekannteren gehören z.B. das Finden der kürzesten Verbindung zwischen zwei Orten (Navigationsystem). Aber darüber hinaus gibt es noch viele andere Probleme die uns zwar ständig begegnen, die wir aber nicht weiter wahrnehmen. Und wieder andere Probleme haben in unserem Alltag keine Relevanz, oder nur in einigen wenigen Fällen.
Aber was ist jetzt eigentlich ein Problem? Ein Problem kann man ganz einfach als die Suche nach der Antwort zu einer Frage beschreiben. Die Frage kann dabei unterschiedlicher Natur sein, zB. wie oben genannt die Frage nach der kürzesten Strecke, um von einem Punkt auf einer Karte zu einem anderen zu kommen. Oder abstrakter formuliert: der Pfad in einem gerichteten und gewichteten Graphen mit den geringesten Kosten c von einem Blatt n zu einem zweiten Blatt n’ über k Kanten.
Jetzt möchten wir Probleme aber zunächst auf möglichst allgemeiner Ebene betrachten. Das ist zunächst schwierig, da es sehr viele unterschiedliche Probleme gibt, deren Lösungen man auf unterschiedliche Art und Weise beschreiben kann oder auch muss. Wir müssen Formalisieren. Anstatt von einem Problem zu reden und nach dessen Lösung zu suchen formulieren wir stattdessen: Ist die gegebene Lösung eine valide Lösung für unser Problem?
Diese Umformulierung verändert nicht die Problemstellung, aber die Antwort auf die Frage wird deutlich vereinfacht. Statt bei jedem Problem Antworten unterschiedlicher Art und Weise zu bekommen, können wir uns jetzt auf die Antworten Ja und Nein einschränken, ohne uns selbst zu beschneiden. Weiter formalisieren wir unser Problem als die Berechnung einer Funktion f(x) mit der Lösung y. Unsere Fragestellung ist jetzt also “ist y = f(x) ?“. Noch formaler sieht das dann so aus:
Ein paar Worte zur Erklärung:
Die Definition ist eine ganz normale Funktionsdefinition, wie man sie auch aus dem Schulunterricht kennen sollte. Auf der linken Seite steht die Basismenge, von der aus wir auf unsere Lösungsmenge (rechts) abbilden. Unsere Lösungsmenge ist in diesem Fall sehr einfach. Da wir vorher festgestellt haben, das wir uns auf die Antworten Ja und Nein beschränken können enthält unsere Lösungsmenge genau zwei Elemente: die 0 als die Antwort Nein und die 1 als Antwort Ja.
Die Menge auf der linken Seite ist schon etwas komplexer. Das * an dieser Stelle ist nicht der übliche Operator für Multiplikation, sondern der Kleene-Star. Die Menge {0,1}* entspricht hier der Menge der möglichen Lösungen des Problems das wir betrachten (diese kann wie hier formal definiert binär codiert sein ohne Einschränkungen in Kauf zu nehmen).
Wichtig ist, dass die Menge {0,1}* eine abzählbar unendliche Menge ist. Das bedeutet, wenn wir uns unendlich viel Zeit nehmen, dann könnten wir alle (unendlich vielen) Elemente der Menge nacheinander aufzählen.
Jetzt haben wir aber nur genau ein Problem und seine möglichen Lösungen betrachtet. Die Menge aller Probleme entspricht der Potenzmenge der Menge {0,1}*. Und gleich hier fangen unsere Probleme an. Denn nach Cantors zweitem Diagonalargument ist die Potenzmenge einer beliebigen Grundmenge stets mächtiger als die Grundmenge (=sie hat mehr Elemente). Da wir aber festgestellt haben, das {0,1}* bereits abzählbar unendlich viele Elemente enthält, muss deren Potenzmenge überabzählbar unendlich viele Elemente enthalten. Eine überabzählbar unendliche Menge bringt jedoch das Problem mit sich, dass wir die Elemente nicht mehr alle aufzählen können (Florian hat hierzu vor ein paar Wochen ein schönes Video verblogt).
Diese Erkenntnis führt uns zu einem Dilemma: Jedes mögliche Computerprogramm besteht aus einer endlichen Folge von Zeichen. Die Menge aller Programme die möglich sind muss also abzählbar unendlich sein. Aber oben haben wir festgestellt, das es überabzählbar unendlich viele Probleme gibt. Die Konsequenz daraus ist die Tatsache, das es mehr Probleme gibt als Lösungen. Es wird also immer Probleme geben, die wir niemals mit einem Computer lösen können.
Kommentare (22)