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)

  1. #1 Faldrian
    21. August 2012

    Schöner Gastbeitrag, dankesehr!
    Besonders die Einleitung hat mir gefallen, denn das ist genau die Erfahrung, die man als Informatikstudent macht – man übt sich darin, Probleme zu lösen, und das merkt man auch im Alltag.
    Dabei die Abstraktion und die Übertragung des Gelernten meiner Meinung nach *die* Qualifikation, die am meisten weiter hilft.

    Auch sonst eine schöne Argumentation… na dann mal weiter im Kampf gegen die Probleme… auch wenn man auf verlorenem Posten steht. Aus mathematischen Gründen. 😉

  2. #2 Alderamin
    21. August 2012

    Danke für den Beitrag, dieses Argument kannte ich noch gar nicht.

    Ein Beispiel für ein unlösbares Problem ist das berühmte “Halteproblem”: hält ein Computerprogramm, angesetzt auf einen bestimmten Input, an oder nicht?

    Dass das Problem nicht universell durch ein Programm lösbar ist, zeigt man durch Widerspruch: Angenommen es gäbe ein Programm P, das für ein anderes, beliebiges Programm Q vorhersagen kann, ob es bei einem bestimmten Input hält oder nicht. Dann kann das Programm insbesondere auf sich selbst als Input angesetzt werden.

    Angenommen, P auf sich selbst angesetzt sagt, P hält. Dann ändern wir P dermaßen in P’ ab, dass P’ nach der Ausgabe der Lösung in eine Endlosschleife läuft. P’ angesetzt auf P’ sagt dann, P’ hält und läuft danach in eine Endlosschleife, Widerspruch. Sollte P’ hingegen auf sich selbst angesetzt sagen, P’ hält nicht, dann folgt nach der Lösungsausgabe keine Endlosschleife und P’ hält. Auch Widerspruch.

    Also ist das Halteproblem unentscheidbar.

    (ich hoffe, ich hab’ das korrekt wiedergegeben, ist schon ein Weilchen her)

  3. #3 Anhaltiner
    21. August 2012

    “Es wird also immer Probleme geben, die wir niemals mit einem Computer lösen können.” – macht doch nichts – die Lösung dieser Probleme ist 42.

  4. #4 Fliegenschubser
    21. August 2012

    Interessanter Beitrag. Als Nicht-Informatiker tauchen allerdings ein paar Fragen auf. Woher weiß ich, dass die Menge der möglichen Lösungen unseres Problems abzählbar unendlich sein muss? Kann die denn nicht auch endlich sein, je nachdem, was für ein Problem ich betrachte? Oder ist das eine Sache der Definition, oder ergibt sich das aus einer Logik, die sich mir verschließt? Denn die Schlussfolgerung, dass niemals alle Probleme mit einem Computer lösbar seinen, ergibt sich ja nur, wenn eben jene Menge (mindestens) abzählbar unendlich viele Elemente hat.
    Ich tu mich damit deshalb ein bischen schwer, weil es nich so ohne weiteres akzeptieren kann/will, dass es grundsätzlich und absolut ausgeschlossen sein soll, dass alle Probleme lösbar sind. Aber vielleicht fehlt mir dazu das mathematische/informatische Grundwissen…

  5. #5 Fliegenschubser
    21. August 2012

    Nach dem Lesen der inzwischen erschienenen Kommentare sehe ich, dass ich wohl mit meiner letzten Vermutung Recht habe^^

  6. #6 7tupel
    21. August 2012

    @Alderamin

    stimmt so. Die TM hält dann an wenn sie nicht hält und umgekehrt wodurch wir einen Widerspruch haben.
    Das hat auch die schöne Folge, dass man niemals ein Programm entwickeln kann welches die Korrektheit eines anderen Programms überprüfen kann (manch ein Entwickler ist schon auf Produkte reingefallen die auf magische Art und Weise die Funktionsfähigkeit der eigenen Software mit absoluter Trefferrate testen).
    Irgendwann werde ich dazu nochmal etwas genauer schreiben und auch auf andere unentscheidbare Probleme wie das Postsche Korrespondenzproblem eingehen (“gibt es eine Folge von Wortpaaren deren paarweise Konkatenation zwei identische Endwörter erzeugt”).

    @Anhaltiner

    das wäre in der Tat schön 😉

  7. #7 Kallewirsch
    21. August 2012

    dass man niemals ein Programm entwickeln kann welches die Korrektheit eines anderen Programms überprüfen kann

    Vorsicht: Das entscheidende Wort hier ist alle. Man kann kein Programm schreiben, welches die Korrektheit aller überhaupt möglicher Programme überprüfen kann. Das schliesst nicht aus, dass das in Einzelfällen geht. Nur eben nicht bei allen.

  8. #8 7tupel
    21. August 2012

    @fliegenschubser

    ich kann deine Skepsis gut verstehen, schließlich möchte man keine Probleme haben die nicht lösbar sind. Ich versuche es zu erklären:
    Die Lösung eines Problems ist wie geschrieben die Berechnung einer Funktion f:{0,1}* -> {0,1}. Dabei ist {0,1}* die Menge aller möglichen Wörter über dem Alphabet {0,1}.
    Die Menge aller Wörter, die Lösungen meines Problems sind bezeichnet man als die Sprache zu dem Problem. Die Sprache ist also eine Teilmenge der Menge {0,1}*.

    Wichtig ist jetzt, dass {0,1}* eine abzählbar unendliche Menge ist. Das kann man relativ einfach zeigen, da die Menge einfach der Menge aller Binärzahlen entspricht, die ja nur aus Nullen und Einsen und deren Zusammensetzung besteht. Binärzahlen sind aber nur eine andere Schreibsweise für Natürliche Zahlen (0, 1, 2, 3, …, unendlich) und diese sind abzählbar unendlich. Formal würde man sagen es gibt eine bijektive Abbildung zwischen der Menge der Binärzahlen und den Natürlichen Zahlen.

    Jetzt müssen wir noch zeigen, dass die Menge der Funktionen f:{0,1}* -> {0,1} überabzählbar ist. Das folgt wie schon erwähnt mit Cantors Zweitem Diagonalargument.

    Denn eine Sprache über dem Alphabet {0,1} (ohne Stern) ist eine Teilmenge von {0,1}* (mit Stern). Eine Teilmenge einer unendlichen Menge kann selbst auch wieder unendlich sein. Wenn wir jetzt die Menge aller Sprachen nehmen, dann kann diese also Elemente (=Sprachen) enthalten die selbst unendlich sind. Und davon wieder unendlich viele. Wir haben also eine “Menge die unendlich viele unendliche Mengen enthält”. Damit muss diese Menge zwangsweise mächtiger sein. Formal zeigt man dies mit Cantors zweitem Diagonalargument. Denn die Menge aller Teilmenge, die hier allen Sprachen entspricht ist die Potenzmenge der Grundmenge (hier {0,1}*). Und diese muss mächtiger sein als die Grundmenge. In unserem Fall wäre das 2 ^ |{0,1}*| = Aleph-1 oder “2 hoch unendlich”

  9. #9 rolak
    21. August 2012

    Kurz & Gut geschrieben, fehlt nur noch mindestens eine url für Random J. Reader: Kleene-Star.

  10. #10 Fliegenschubser
    21. August 2012

    Vielen Dank für diese ausführlichere Erklärung, das hat mir tatsächlich weitergeholfen.

  11. #11 Anhaltiner
    21. August 2012

    @7tupel Wenn ich mir gerade keinen Stress mit unendlichen und unendlich mal unendlich machen will kann ich dann auch sagen “Es gibt deutlich mehr als 10 Rechnungen die als Ergebnis die 10 einstelligen natürlichen Zahlen haben – bei 4 Grundrechenarten alleine 4 verschiedene f(x)=x, bei 10 Zahlen also 40 Rechnungen!”

  12. #12 Dirk
    21. August 2012

    Man kann sich Probleme MACHEN, oder Probleme LÖSEN.

    Ich bin ein freund von letzterem.

  13. #13 StefanL
    22. August 2012

    @7tupel

    Wir haben also eine “Menge die unendlich viele unendliche Mengen enthält”. Damit muss diese Menge zwangsweise mächtiger sein.

    Ähm- nein. Nehmen wir die Natürlichen Zahlen … dann die Teilmenge der durch 2 teilbaren Zahlen , dann die Teilmenge der übriggebliebenen die durch 3 teilbar sind , dann die restlichen die durch 5 teilbar sind usw. da wir unendlich viele Primzahlen haben und in jeder dieser “Prim”-teilmengen unendlich viele Zahlen sind haben wir unendlich viele (disjunkte) Teilmengen die alle unendlich “mächtig” sind und trotzdem nur eine Teilmenge der Menge der Natürlichen Zahlen ( die 1 und die 0 sind ja nicht dabei) die kaum mächtiger als sie selbst ist.
    Der “Satz von Cantor” das eine Potenzmenge P(A) mächtiger als A ist liegt daran, daß jede Abbildung f: A->P(A) nicht surjektiv ist.
    Hilfreich ist möglicherweise auch bei {0,1}* daraufhinzuweisen, daß die Abzählbarkeit dadurch erzielt wird, daß nur endliche Folgen von 0 und 1 “erlaubt” sind.

  14. #14 Der Kontrolleur
    22. August 2012

    Ja genau…am Anfang war das Problem und das nannte sich Astrodicticum Simplex, ein Hetz-Blog gegen Esoteriker. Nun ja…bloß weil man keine Werte mehr hat muss man das nicht an Andersgläubigen auslassen die noch Werte haben, gell?

  15. #15 pete
    22. August 2012

    @Der Kontrolleur
    Na na na … so schlimm ist es nun auch wieder nicht. Die meinen es wirklich gut.

  16. #16 psiram_fan
    22. August 2012

    ein Hetz-Blog gegen Esoteriker.

    Es kann nur einen geben! Und das ist der Blog von Psiram / Esowatch! Hier dieser trockene wissenschaftliche Blog, der sogar noch ein echtes Impressum hat und wo man den Blogger sogar noch persönlich anmachen kann – das ist doch nur Kokolores 🙂

    Ein echter Hetzblog muss mindestens im Nirgendwo gehostet werden, zig Prozesse am Hals haben (wenn auch erfundene) und ein Kopfgeld sollte auch ausgesetzt sein… da ist dieser seriöse Blog aber auch kilometerweit von entfernt…

    Florian, sieh zu das es so bleibt!

  17. #17 Florian Freistetter
    22. August 2012

    @Kontrolleur: “Ja genau…am Anfang war das Problem und das nannte sich Astrodicticum Simplex, ein Hetz-Blog gegen Esoteriker.”

    Kleiner Hinweis: “Hetze” ist was anderes als “Kritik”. Bis auf den Buchstaben “t” ist da nichts gleich.

  18. #18 7tupel
    22. August 2012

    @StefanL

    Stimmt, meine Formulierung an dieser Stelle war falsch. Klar kann ich die Menge der Natürlichen Zahlen auf Basis der Primzahlen in Restklassen zerlegen. Da es unendlich viele Primzahlen gibt muss es unendlich viele solcher Restklassen geben die jeweils wieder unendlich viele Elemente enthalten (eben alle positiven ganzzahligen Vielfachen der Primzahl).
    Der Trick bei der Potenzmenge ist das es sich dabei um die Menge handelt, die alle Teilmengen der Ausgangsmenge enthält. Und in dieser Menge kann man nicht mehr alle Elemente nacheinander aufzählen, die besagte surjektive Abbildung ausgehend von den Natürlichen Zahlen gibt es hier nicht.

  19. #19 noch'n Flo
    22. August 2012

    Und da isser schon wieder – der Stinker mit den ständig wechselnden Namen.

    Ach ja, und zum Blogthema – mich wundert, dass es hier noch nicht gesagt wurde, deshalb eine ganz wichtige Weisheit:

    Computer helfen uns, Probleme zu lösen, die wir ohne sie gar nicht hätten.

    😉

  20. #20 rnlf
    23. August 2012

    @Anhaltiner: Tut mir leid, du irrst dich. Das Ergebnis ist zwar 42, wurde aber VON EINEM COMPUTER berechnet. Tja. Schachmatt, versenkt und Bingo!

  21. #21 Snofru
    23. August 2012

    Jetzt muss ich doch auch mal was anmerken 🙂

    Der Weg über die möglichen Sprachen ist gar nicht nötig. Es reicht zu zeigen, dass es überabzählbare viele Funktionen gibt. Gemacht wird es wieder mit Diagonalisierung. Das Hauptargument ist jetzt aber (und das fehlte mir bisher), dass es nur abzähbar viele Programme (eigentlich Turing-Maschinen) gibt. Es lässt sich also nicht zu jeder Funktion auch ein passendes Programm schreiben, was sie berechnet.

  22. #22 Snofru
    23. August 2012

    Arr.. beim ganzen Kommentare lesen vergessen, dass es ja am ende des Artikels sogar steht 🙁

    Die Diagonalisierung klappt trotzdem ohne Sprachen 😉