Welches Adjektiv beschreibt einen Informatiker am besten? “Informatiker sind faul” — meinte letztens ein guter Freund (seinerseits ebenfalls Informatiker) zu mir. Was er damit sagen wollte? In erster Linie, dass Informatiker lieber einem Computer beibringen, ein Problem zu lösen, als es selbst zu lösen. Da stellt sich die Frage: Kann man alle Probleme mit dem Computer lösen?

Comic von xkcd (CC BY-NC 2.5)

Comic von xkcd (CC BY-NC 2.5)

Um diese Frage zu beantworten gibt es in der Informatik das Konzept der Berechenbarkeit. Ein Problem ist dann berechenbar (also von einem Computer lösbar), wenn man dafür einen Algorithmus schreiben kann. Um zu testen, ob ein Problem berechenbar ist, gibt es verschiedene Modelle. Eines davon ist die Turing-Maschine, von der ich euch hier schon berichtet habe. Turing-Maschinen sind nicht real existierend, sondern ein Konzept, welches man sich folgendermaßen vorstellen kann: man hat ein unendlich langes Tape oder einen unendlich langen Streifen Papier, der in aneinandergereihte, einzelne Felder unterteilt ist. Außerdem hat die Maschine einen Lese-/Schreibkopf, den man entlang des Bandes bewegen kann. Eine Turing-Maschine hat drei Funktionen: Lesen, Schreiben und den Kopf bewegen.

Für jedes Problem, das berechenbar ist, kann man sich eine solche Maschine ausdenken, die nur durch diese drei Funktionen das Problem lösen kann und irgendwann anhält. Der Kopf kann dabei verschiedene Zustände annehmen. Für jeden Zustand gibt es eine Anweisung, was die Maschine als nächstes tut. Diese Anweisung besteht aus “Lesen, Schreiben, Kopf-Bewegen, Zustand ändern”. Zu Beginn ist das Band mit Nullen gefüllt. Eine mögliche Anweisung für Zustand 1 wäre “wenn eine Null auf dem Band steht, schreibe eine Eins, rücke ein Feld nach rechts, gehe in Zustand 2”. Die Beschreibung dieser Zustände und der durchzuführenden Aktionen, entspricht dem Algorithmus zur Lösung des Problems. Wichtig ist dabei, dass es einen Haltezustand gibt, in den die Maschine irgendwann läuft.

Eine Turing-Maschine für den fleißigsten Biber mit zwei Zuständen. Die Maschine schreibt vier Einsen.

Eine Turing-Maschine für den fleißigsten Biber mit zwei Zuständen. Die Maschine schreibt vier Einsen.

Der fleißige Biber

Stellen wir uns jetzt eine Turing-Maschine vor, die folgendes Problem lösen soll, schreibe maximal viele Einsen auf das Band und stoppe dann. Hätte diese Maschine nur einen Zustand, könnte sie nur eine einzige Eins schreiben. Dieser Zustand wäre zum Beispiel: “wenn eine Null auf dem Band steht, schreibe eine Eins, rücke ein Feld nach rechts, halte an”. Würde die Maschine wieder in den selben Zustand gehen, statt anzuhalten, würde sie unendlich viele Einsen auf das Band schreiben und niemals anhalten. Eine Turing-Maschine mit zwei Zuständen kann maximal vier Einsen auf das Band schreiben, eine mit drei Zuständen maximal sechs Einsen.

Die beschriebenen Turing-Maschinen heißen fleißige Biber. Warum? Man will sozusagen die fleißigste Turing-Maschine finden, also die, die die meisten Einsen schreibt, bevor sie anhält. Könnte man sich jetzt eine Turing-Maschine ausdenken, die berechnet, wie viele Einsen der fleißigste Biber für n Zustände schreibt? Nein, leider kann man das nicht. Warum? Wir müssten uns zuerst alle Turing-Maschinen mit n Zuständen überlegen und dann alle durchtesten, wie viele Einsen sie schreiben, um den fleißigsten Biber zu finden. Das Problem ist: Solange der Biber Einsen schreibt, woher sollen wir wissen, ob er noch anhalten wird oder niemals stoppt?

Das Halteproblem

Kann man überhaupt feststellen, ob ein Algorithmus jemals stoppt? Ist das Problem “Hält der Algorithmus X auf Eingabe Y” berechenbar? Kann man einen Über-Algorithmus schreiben, der für alle möglichen Algorithmen und beliebige Eingaben bestimmt, ob der Algorithmus stoppt? Wie müsste ein solcher Über-Algorithmus aussehen? Nein, kann man nicht. Bewiesen hat das Alan Turing mittels seiner Turing-Maschinen und schön nachvollziehen lässt sich das anhand eines Widerspruchs.

Was bedeutet das praktisch? Es gibt also Probleme, deren Lösungen sogar wohl definiert sind (zum Beispiel die maximale Anzahl an Einsen, die der fleißigste Biber schreibt), die man aber mit dem Computer nicht berechnen kann. Und zwar mit keinem Computer, auch keinem, der vielleicht in der Zukunft entwickelt wird (vorausgesetzt er liest und schriebt Zeichen auf einem Speicher). Immerhin weiß der faule Informatiker dann, dass er es auch gar nicht erst versuchen muss. Aber selbst wenn ein Problem algorithmisch lösbar (also berechenbar) ist, ist es in erster Linie theoretisch lösbar. Algorithmisch lösbar bedeutet aber noch längst nicht, dass das Problem auch “praktisch lösbar” ist. Aber dazu erzähle ich euch ein andermal mehr.


Beitrag auf BioinfoWelten lesen.

Kommentare (14)

  1. #1 rolak
    21. Juni 2016

    Heidewitzka – nach dem Wechsel zur Informatik wurde ich binnen eines Jahres eingezogen, konnte aber die Panzergrenadiererei durch eine die Rückstellung abschließende Verhandlung in den schon vorher avisierten Zivildienst umtauschen. So gings dann 2.Hälfte 80er mit Moped, Baß, Rechner und Kassettensammlung in die Jugendherberge — und Elektor veranstaltete irgendwann einen Wettbewerb über iirc 5zuständige Biber. Also wurde Donnerstags eine Turingmaschine geschrieben und ein wenig probiert, Freitags ein Programm, das die TuringBiber durchtestet – und beim Überlegen, wie denn die Maschinen am günstigsten aufzählbar seien dämmerte mir, daß der Ansatz dem berühmten Widerspruchsbeweis des Halteproblems verdächtig ähnelte…

    Also Samstag morgens in die Bibliothek, ahja, eines der nichthaltenden Probleme. Dann wars ab nachmittags doch wesentlich unbeschwerter auf der Party, auch wenn dadurch die Nacht auf Montag unangenehm kurz wurde ;‑)

  2. #2 Laie
    22. Juni 2016

    Das Problem der Berechenbarkeit ließe sich nicht mal mit unendlicher Zeit(dauer) lösen, da dadurch nicht nur die Stromrechnung ins Unermessliche steigt, sondern die Turinmaschine irgendwann dazwischen (vor unendlich) kaputtgeht, und wer könnte schon das Servicepersonal für eine Ewigkeit bereitstellen, und wer zahl den Strom? 🙂

  3. #3 schlappohr
    22. Juni 2016

    “Solange der Biber Einsen schreibt, woher sollen wir wissen, ob er noch anhalten wird oder niemals stoppt?”

    Hier habe ein bisschen gestutzt. Du bringst hier den Aspekt der Zeit ins Spiel, aber im Turing-Modell existiert eigentlich keine Zeit, oder? Ist schon ein paar Jahre her, aber soweit ich mich erinnere, ist eine theoretische TM gewissermaßen unendlich schnell, d.h. sie terminiert sofort, und wenn sie nicht sofort terminiert, dann tut sie es niemals. Es ergibt also eigentlich keinen Sinn, auf irgendetwas zu warten.
    Das Problem ist eigentlich das folgende: Der hypothetische Über-Algorithmus ist selbst ein Turing-Programm, dass nacheinander alle n-state-Turingprogramme durchrechnet. Wenn eines dieser Programme nicht terminiert, dann terminiert auch der Über-Algorithmus nicht, d.h. er kann anschließend keine Biber-Einsen mehr zählen und liefert somit kein Ergebnis. Vermutlich meinst Du genau das.

    • #4 rolak
      22. Juni 2016

      den Aspekt der Zeit ins Spiel, aber im Turing-Modell existiert eigentlich keine Zeit, oder?

      Zeiteinheit=1Takt bzw ein Zustandswechsel, schlappohr, und zwar unabhängig davon, wie lange nun ein Takt dauert (also inkl 0). Relevant ist zumeist tatsächlich nur die Antwort auf die Frage, ob das Teil beim gegebenen Input stoppt oder ewig weiterklappert – beim EffizienzVergleich zweier Algorithmen allerdings ist die ~Zeit wesentlich.

  4. #5 Dr. Webbaer
    22. Juni 2016

    Howdy!

    Nur ein paar Anmerkungen:
    1.) Mathematiker sind bereits ‘faul’ und ihnen zuvorkommend bereits einige Philosophen, wobei sie nicht wirklich ‘faul’ sind, sondern sparsam.
    2.) Hierzu – ‘Kann man alle Probleme mit dem Computer lösen?’ -. also Probleme, sollten sie weltlicher oder im Speziellen sozialer Art sein, können durch Software nicht gelöst, sondern nur unterstützt werden in ihrer Bearbeitung bis ‘Lösung’.
    Auch rein mathematisch oder weitergehend tautologische Probleme, also nicht-weltliche, können regelmäßig vom Rechner und mit Software nicht gelöst werden.
    3.) Das ‘Halteproblem’ wird im Rahmen eines sozusagen robusten Software-Einsatzes regelmäßig umgangen, indem eine Routine austimen kann, dann sozusagen extern gestoppt wird, natürlich ohne (positives) Ergebnis.

    MFG + viel Erfolg!
    Dr. Webbaer

  5. #6 kalo
    22. Juni 2016

    Müßte nicht in der Zustandstabelle im gezeigten Schema unter “Bewegung” in der zweiten Zeile “nach links” stehen? Sonst hält doch dieser Algorithmus nie! – Oder verstehe ich das hier unterstellte Zustandskonzept nicht?

    • #7 Franziska Hufsky
      22. Juni 2016

      Die Abbildung stimmt. Hier die Arbeitsweise:
      Arbeitsweise des fleißigen Bibers für zwei Zustände

  6. #8 kalo
    22. Juni 2016

    Ah, ja. Hatte nicht zu Ende gedacht.

  7. #9 Braunschweiger
    22. Juni 2016

    @Laie ~#2:
    Das war Satire oder verar…nd gemeint, oder?
    Eine Turingmaschine geht nicht kaputt und verbraucht keinen Strom, und eigentlich auch keine Zeit. Ich schreibe das, weil ich unterstreichen möchte, dass so eine Turingmaschine ein theoretisches Modell ist.

    @schlappohr:
    Eigentlich hast du recht, und der Begriff einer “Zeit” ist meiner Meinung nach eine praktische Vereinfachung. Eine Turingmaschine produziert eine Folge von Zuständen (die, die sie durchläuft — neben der Bandausgabe), die entweder beim Stopp abbricht und endlich ist, oder aber die unendlich ist. Egal, welche Zeitspanne ungleich 0 du einem Schritt zuordnest: wenn die Verarbeitung nicht abbricht, läuft sie dann unendlich. Unendliche Folgen sind mathematische Objekte.

    Das Problem mit der Zustandsfolge ist, dass man eine wirklich unendliche und explizit hingeschriebene Zustandsfolge nicht handhaben könnte. Man kann sie ja eben nicht in endlicher Zeit schreiben oder lesen. Also behilft man sich mit der Vorstellung, dass eine Turingmaschine eine solche unendliche Folge “gerade eben produziert”, und man sieht zumindest, dass noch nicht gestoppt wurde. Es ist aber unzulässig mit Zeit zu argumentieren (“wenn die TM in x Sekunden nicht fertig ist…”), weil immer Fälle denkbar sind, in denen trotz endlicher Folge bis x noch kein Abbruch erfolgt, egal welche Größe x hat.

  8. #10 Laie
    23. Juni 2016

    @Braunschweiger
    Weder, noch!

    … der Witz oben bei mir soll sein, eine Turingmaschine kann man ja nicht wirklich (sinnvoll mechanisch)* nachbauen – da es eine theoretisches Modell ist -, jedoch in Computern simulierbar, bzw. fast-Äquivalenz zu bestehenden Computern herstellbar ist bezüglich Berechenbarkeit, die benötigen Strom und Rechenzeit, sind also nicht so schnell. Und einen unendlichen Speicher gibts halt auch nicht in Computern…
    Geht denn das nicht aus dem Geschriebenen deutlichst hervor?

    * Es hat sogar jemand mal aus Liebe zur Sache eine mechanische Turing-Maschine gebaut, jedoch mit endlichem Band.

    Anderes Beispiel: Verschicke einen Witz mit der Deutschen Bahn: Problem, er kommt nicht an.

  9. #11 schlappohr
    23. Juni 2016

    ” Also behilft man sich mit der Vorstellung, dass eine Turingmaschine eine solche unendliche Folge “gerade eben produziert”, und man sieht zumindest, dass noch nicht gestoppt wurde. ”

    Das sieht man von “außen” als Beobachter, aber der Beobachter ist nicht Teil der Turingmaschine und auch nicht Teil des Beweises. Die TM selbst kann hingegen nur feststellen, dass ein TM-Programm terminiert, aber nicht, dass es nicht terminiert. In einer “echten” Software würde man sagen, dass der Funktionsaufruf nicht zurück kommt.

    Zu meiner Schande muss ich gestehen, dass ich das Vordiplom in Theoretischer Informatik im ersten Versuch versemmelt habe und die Prüfung nach einem Semester bei einem anderen Lehrstuhl wiederholen musste. Dieser Professor hat anstelle der TM die Klasse der µ-rekursiven Funktionen bevorzugt. im Nachhinein war es sehr hilfreich, beides kennen zu lernen. Diese Modelle sind äquivalent, aber irgendwie kam ich mit den µ-rek. Funktionen besser zurecht (was sich auch in einem recht gut bestandenen VDP zeigte). Die Frage, wann eine Maschine mit einer Berechnung fertig wird, stellt sich hier nicht, weil es keine Maschine gibt 🙂 Zudem fand ich die Vorstellung von einer Maschine, die unendlich schnell auf einem unendlich langen Papierstreifen schreibt, irgendwie unbehaglich.

  10. […] wenn ihr die Münzen vorher sortiert. Aber wie gesagt, ihr seid faul (vermutlich seid ihr Informatiker). Also brauchen wir einen Algorithmus, der uns das gemessene Gewicht zerlegt, in die Anzahl der […]

  11. […] ein paar Wochen habe ich euch das Konzept der Berechenbarkeit in der Informatik vorgestellt. Damit lässt sich die Frage beantworten, ob ein Problem berechenbar ist oder nicht. […]

  12. […] Beitrag auf ScienceBlogs lesen. […]