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

Beispiel

Verbinden 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-RasterNeun 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ösbar

Ein 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

Beispiel

Halten diese drei Programme an? Das dritte beginnt mit einer beliebigen natürlichen Zahl n.

n = 5
while n > 0:
    n = n - 1
n = 5
while n > 0:
    n = n + 1
while n != 1:
    if n % 2 == 0:
        n = n // 2
    else:
        n = 3 * n + 1
Die Vermutung von Collatz

Das 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ösbar

Nehmen wir an, es gäbe eine Funktion haelt(p, e), die für jedes Programm p und jede Eingabe e nach endlich vielen Schritten richtig antwortet, ob p bei Eingabe e anhält. Mit ihr bauen wir ein neues Programm:

def seltsam(p):
    if haelt(p, p):
        while True:
            pass
    else:
        return

Nun geben wir seltsam sich selbst als Eingabe. Hält seltsam(seltsam) an?

Was dabei nicht behauptet wird

Fü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 Satz

Alles, 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 nn 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 BB(n)\text{BB}(n).

nn1234
BB(n)\text{BB}(n)1621107

Für n=5n = 5 ist BB(5)=47 176 870\text{BB}(5) = 47\,176\,870. Diesen Wert hat eine Gruppe von Freiwilligen erst im Juli 2024 bewiesen, dreiundsechzig Jahre nach der Fragestellung. Für n=6n = 6 kennt niemand die Antwort, und man weiss, dass sie jede vorstellbare Grösse übersteigt.

Die Folge BB(n)\text{BB}(n) 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 nn Zuständen einfach BB(n)\text{BB}(n) Schritte laufen und wüsste danach Bescheid.

Ausblick auf die 6. Klasse

Bis 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.1

Sagen Sie zu jedem Programm, ob es anhält, und begründen Sie kurz.

k = 1
while k < 100:
    k = k * 2
k = 100
while k != 0:
    k = k - 3
k = 1
while k > 0:
    k = k * 2
Aufgabe 6.5.2

Erzä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.3

Ist 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.4

Jemand 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.5

Erklären Sie, warum sich BB(n)\text{BB}(n) nicht berechnen lässt. Nehmen Sie an, es gäbe ein Programm dafür, und überlegen Sie, was man damit anstellen könnte.