{"id":4145,"date":"2013-04-25T08:31:22","date_gmt":"2013-04-25T06:31:22","guid":{"rendered":"https:\/\/www.herr-rau.de\/wordpress\/?p=4145"},"modified":"2026-01-22T17:57:41","modified_gmt":"2026-01-22T16:57:41","slug":"das-halteproblem","status":"publish","type":"post","link":"https:\/\/www.herr-rau.de\/wordpress\/2013\/04\/das-halteproblem.htm","title":{"rendered":"Das Halteproblem"},"content":{"rendered":"
(7 Kommentare.<\/a>)<\/small> <\/div>\n

Zum Abitur und im Semester davor schreiben die Sch\u00fcler in Informatik Computerprogramme in einer Assembler-Programmiersprache. Die besteht zwar aus ganz einfachen Einzelschritten, aber genau das f\u00fchrt dazu, dass das ganze Programm etwas un\u00fcbersichtlich ist und man nicht auf den ersten Blick sieht, was es genau tut. Wenn ich die Sch\u00fclerprogramme also bewerten will, muss ich sie abtippen und laufen lassen, und dann sehe ich, ob am Schluss das richtige Ergebnis herauskommt. Wenn ja: volle Punktzahl, wenn nein: puh. Dann muss ich das Programm Schritt f\u00fcr Schritt nachvollziehen, um herauszufinden, wo das Problem ist – wo sich zum Beispiel eine Endlosschleife verbirgt, so dass das Programm nie aufh\u00f6rt zu laufen.<\/p>\n\n\n\n

In dieser Situation w\u00fcnschte ich mir ein Programm, das diese Arbeit automatisch f\u00fcr mich erledigt. Ich w\u00fcrde es mit den Sch\u00fclerprogrammen f\u00fcttern, und es w\u00fcrde mir danach sagen „ja, das Programm kommt fr\u00fcher oder sp\u00e4ter an ein Ende“ oder „nein, das Programm wird in eine Endlosschleife geraten und nie aufh\u00f6ren“ oder „das Programm kann in eine Endlosschleife geraten, je nach Startwert.“<\/p>\n\n\n\n

Die Frage, ob es so ein Programm gibt, hei\u00dft Halteproblem<\/strong> der Informatik. Und das Halteproblem ist allgemein nicht l\u00f6sbar – es kann<\/em> so ein Programm nicht geben, egal wie gut Computer noch werden. (F\u00fcr spezielle Sonderf\u00e4lle, etwa Programme, die sich an bestimmte Vorgaben halten, ist es oft l\u00f6sbar. Aber eben nicht, wenn es um beliebige Programme geht.)<\/p>\n\n\n\n

Der Beweis folgt.<\/p>\n\n\n\n

Teil 1: Was ein Computerprogramm ist.<\/h3>\n\n\n\n

Ein Computerprogramm kann man sich als ein Frage-Antwort-Maschinchen vorstellen, in das man zum Beispiel eine Zahl eingibt, dann rechnet das Maschinchen, um am Schluss macht es „Ping!“ und eine Zahl kommt als Antwort heraus. Da gibt es zum Beispiel das Verdoppelungsmaschinchen:<\/p>\n\n\n\n

verdoppeln(eines eingangswertes):\n  ergebnis: eingangswert mal 2<\/code><\/pre>\n\n\n\n
Das funktioniert nat\u00fcrlich nicht nur mit Zahlen, sondern auch mit Text. Lehrer tr\u00e4umen ja von einem Korrektur- und Benotungsmaschinchen:<\/p>\n\n\n\n
benoten(eines aufsatzes):\n  (rechnen, rechnen, rechnen)\n  ergebnis: note<\/code><\/pre>\n\n\n\n
Die praktische Schwierigkeit liegt dabei in dem Schritt, den ich weggelassen habe: das mit dem Rechnen. Um das geht es hier aber gar nicht. Wie<\/em> der Computer vorgeht, um zum gew\u00fcnschten Ergebnis zu kommen, interessiert uns im Moment nicht. Wichtig ist nur, dass ein Programm zum Berechnen eine Wiederholungsschleife ausf\u00fchren kann, dass ein Programmteil also immer und immer wiederholt wird, bis eine bestimmte Bedingung (die Wiederholbedingung) nicht mehr gilt. Bei den meisten \u00fcblichen Berechnungen kann man vorher sagen, wie oft das h\u00f6chstens der Fall sein wird, bei anderen Berechnungen ist das schwieriger.<\/p>\n\n\n\n
Um das zu veranschaulichen, verwende ich drei Beispielprogramme, auf die ich auch sp\u00e4ter zur\u00fcckkommen werde. Die Programme sind countdown (von einer beliebigen Startzahl aus), endlosdrucken (eines beliebigen Starttextes)<\/code> und ausdrucken(eines beliebigen Starttextes)<\/code>.<\/p>\n\n\n\n
Mein erstes Programm ist eigentlich nur ein kleines Hilfsprogramm:<\/p>\n\n\n\n
Ausdruckprogramm<\/h4>\n\n\n\n
ausdrucken(eines Textes):\n  druckt den Text aus<\/code><\/pre>\n\n\n\n
Jetzt die anderen Progr\u00e4mmchen:<\/p>\n\n\n\n
Countdownprogramm<\/h4>\n\n\n\n
countdown(von einer Zahl aus):\n  wiederhole solange zahl>0:\n    ausdrucken(der zahl)\n    um_eins_verringern(die zahl)<\/code><\/pre>\n\n\n\n
Man sieht sehr schnell, wie lange dieses Countdown-Programm braucht, bis es fertig ist: Wenn ich mit der Zahl 5 anfange, sind es 5 Durchg\u00e4nge durch die Schleife, mit jeweils sinkender Zahl (5-4-3-2-1).<\/p>\n\n\n\n
Merke: Dieses Programm kommt immer fr\u00fcher oder sp\u00e4ter zu einem Ende, egal mit welcher Startzahl ich anfange.<\/p>\n\n\n\n
Endlosdrucker<\/h4>\n\n\n\n
endlosdrucken(eines Textes):\n  wiederhole solange Textl\u00e4nge gr\u00f6\u00dfer als -1:\n    ausdrucken(des Textes)<\/code><\/pre>\n\n\n\n
Man sieht schnell, dass dieses Programm nie zu einem Ende kommt. Es wird immer wieder den gleichen Text ausdrucken.<\/p>\n\n\n\n
Merke: Dieses Programm kommt nie zu einem Ende, egal mit welchem Starttext ich anfange.<\/p>\n\n\n\n
Und der Vollst\u00e4ndigkeit halber: Es gibt nat\u00fcrlich auch viele Programme, bei denen es vom Startwert abh\u00e4ngt, ob das Programm ewig l\u00e4uft oder nicht. Hier ein ganz simples Beispiel:<\/p>\n\n\n\n
manchmalprogramm(text):\n  wiederhole solange Textl\u00e4nge > 5:\n    ausdrucken(text)<\/code><\/pre>\n\n\n\n
Das Programm druckt den Eingabetext immer und immer wieder aus und h\u00f6rt nie auf – es sei denn, der Eingabetext ist k\u00fcrzer als 5 Zeichen lang. Dann tut das Programm gar nichts.<\/p>\n\n\n\n
Wir merken uns:<\/b><\/p>\n\n\n\n
    \n
  1. Manche Programme terminieren (kommen zu einem Ende), andere nicht (sind in einer Endlosschleife gefangen).<\/li>\n\n\n\n
  2. Ob sie das eine oder andere tun, h\u00e4ngt auch von den Eingabewerten ab, mit denen das Programm aufgerufen wird.<\/li>\n\n\n\n
  3. Bei einfachen Programmen sieht man sehr schnell, wann sie terminieren oder nicht.<\/li>\n\n\n\n
  4. Bei komplizierten Programmen geht das nicht so einfach, oder gar nicht.<\/li>\n<\/ol>\n\n\n\n
    Teil 2: Noch ein Beispiel, warum es sch\u00f6n w\u00e4re, wenn das Halteproblem l\u00f6sbar w\u00e4re.<\/h3>\n\n\n\n
    Es gibt mathematische Probleme, bei denen wei\u00df man die L\u00f6sung nicht. Man wei\u00df nicht einmal, ob es eine L\u00f6sung gibt. Etwa bei der wiederholten Anwendung der Collatz-Funktion. Die geht so: Beginne mit einer nat\u00fcrlichen Zahl. Wenn sie gerade ist, halbiere sie; wenn sie ungerade ist, multipliziere sie mit 3 und addiere 1. Wiederhole das mit der neuen Zahlen, die du erhalten hast – und dann immer weiter.<\/p>\n\n\n\n