Nach einem Skript von Philipp Moor (Kantonsschule Zimmerberg).
Lernziele
- Unterscheiden zwischen «ich finde keine Lösung» und «es gibt keine Lösung»
- Erklären, was das Halteproblem ist
- Das Widerspruchsargument in eigenen Worten wiedergeben
- Sagen, was die Church-Turing-These behauptet und warum sie eine These ist und kein Satz
5 Was heisst überhaupt lösbar?
5.1 Das Neun-Punkte-Problem
BeispielVerbinden Sie die neun Punkte mit vier geraden Strichen, ohne den Stift abzusetzen. Jeder Strich beginnt dort, wo der vorige aufgehört hat.
Neun Punkte in einem 3×3-Raster
Zwei ganz verschiedene Sätze«Ich finde keine Lösung» sagt etwas über mich aus. «Es gibt keine Lösung» sagt etwas über das Problem aus. Der zweite Satz ist viel stärker, und man kann ihn nur behaupten, wenn man ihn beweist. Beim Neun-Punkte-Problem wäre er falsch gewesen.
5.2 Algorithmisch lösbar
Definition: algorithmisch lösbarEin Problem heisst algorithmisch lösbar, wenn es ein Verfahren gibt, das
Im nächsten Kapitel kommt ein Problem, von dem sich beweisen lässt, dass es kein solches Verfahren gibt. Nicht heute noch nicht, sondern nie.
6 Das Halteproblem
6.1 Endlosschleifen
BeispielHalten diese drei Programme an? Das dritte beginnt mit einer beliebigen natürlichen Zahl
n.n = 5 while n > 0: n = n - 1n = 5 while n > 0: n = n + 1while n != 1: if n % 2 == 0: n = n // 2 else: n = 3 * n + 1
Die Vermutung von CollatzDas dritte Programm gehört zu einer Frage, die 1937 gestellt wurde und seither offen ist. Man hat sie für alle Zahlen bis weit über eine Trillion geprüft, ohne Gegenbeispiel. Ein Beweis fehlt trotzdem.
6.2 Der Widerspruch
Es wäre praktisch, ein Programm zu haben, das jedem anderen Programm ansieht, ob es anhält. Man könnte damit Endlosschleifen finden, bevor sie stören. Turing hat 1936 gezeigt, dass es ein solches Programm nicht geben kann.
Das Halteproblem ist unlösbarNehmen wir an, es gäbe eine Funktion
haelt(p, e), die für jedes Programmpund jede Eingabeenach endlich vielen Schritten richtig antwortet, obpbei Eingabeeanhält. Mit ihr bauen wir ein neues Programm:def seltsam(p): if haelt(p, p): while True: pass else: returnNun geben wir
seltsamsich selbst als Eingabe. Hältseltsam(seltsam)an?
Was dabei nicht behauptet wirdFür viele einzelne Programme sieht man dem Code sofort an, ob er hält. Unmöglich ist nur ein Verfahren, das es für jedes Programm schafft. Genau das verlangt die Definition aus Unterkapitel 5.2.
6.3 Die Church-Turing-These
Eine These, kein SatzAlles, was sich überhaupt planmässig berechnen lässt, kann auch eine Turingmaschine berechnen.
6.4 Fleissige Biber
Wie lange kann eine kleine Maschine laufen?Eine Turingmaschine mit Zuständen, die auf leerem Band startet, hält entweder irgendwann oder nie. Unter denen, die halten, sucht man die fleissigste: diejenige mit den meisten Schritten. Diese Zahl heisst .
1 2 3 4 1 6 21 107 Für ist . Diesen Wert hat eine Gruppe von Freiwilligen erst im Juli 2024 bewiesen, dreiundsechzig Jahre nach der Fragestellung. Für kennt niemand die Antwort, und man weiss, dass sie jede vorstellbare Grösse übersteigt.
Die Folge wächst schneller als jede Funktion, die sich berechnen lässt. Könnte man sie berechnen, so hätte man auch das Halteproblem gelöst: man liesse jede Maschine mit Zuständen einfach Schritte laufen und wüsste danach Bescheid.
Ausblick auf die 6. KlasseBis hierher ging es um die Frage, ob ein Problem überhaupt lösbar ist. In der 6. Klasse kommt die nächste Frage: wie teuer ist die Lösung? Dort lernen Sie, den Aufwand eines Verfahrens abzuschätzen, und Sie werden Probleme treffen, die zwar lösbar sind, für die aber jedes bekannte Verfahren zu lange braucht.
6.5 Aufgaben
Aufgabe 6.5.1Sagen Sie zu jedem Programm, ob es anhält, und begründen Sie kurz.
k = 1 while k < 100: k = k * 2k = 100 while k != 0: k = k - 3k = 1 while k > 0: k = k * 2
Aufgabe 6.5.2Erzählen Sie das Argument aus Unterkapitel 6.2 in eigenen Worten nach. Gehen Sie dabei auf beide Fälle ein und sagen Sie am Schluss, welche Annahme falsch war.
Aufgabe 6.5.3Ist die Aussage richtig oder falsch? Begründen Sie mit einem Satz.
(a) Man kann von keinem Programm sagen, ob es anhält.
(b) Mit einem schnelleren Computer liesse sich das Halteproblem lösen.
(c) Es gibt Fragen, auf die kein Computer je eine Antwort finden wird.
Weitere Aufgaben
Zusatzaufgabe 6.5.4Jemand schlägt vor: «Um herauszufinden, ob ein Programm anhält, lasse ich es einfach laufen und schaue zu.» Erklären Sie, warum dieses Verfahren die Definition aus Unterkapitel 5.2 nicht erfüllt.
Zusatzaufgabe 6.5.5Erklären Sie, warum sich nicht berechnen lässt. Nehmen Sie an, es gäbe ein Programm dafür, und überlegen Sie, was man damit anstellen könnte.