Ein Prüfprogramm, das jeden Absturz vorhersagt
Das Halteproblem fragt, ob ein Programm bei einer Eingabe irgendwann anhält oder für immer läuft. Kein Programm kann diese Frage für alle anderen Programme richtig beantworten. Das ist bewiesen und kein Mangel heutiger Rechner.
Eine Softwarefirma würde gern ein Werkzeug verkaufen, das jede Endlosschleife vorab findet. Diese Lektion zeigt, warum es das nie geben wird, und was zu langsam bedeutet.
Am Ende dieser Lektion
Notiz
Ich kann erklären, warum kein Programm jede Frage entscheiden kann und was „zu langsam“ heißt.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Entscheidbar | ein Programm beantwortet jede Frage dieser Art richtig und hält an | |
| Unentscheidbar | kein Programm kann alle Fragen dieser Art richtig beantworten | |
| Halteproblem | die Frage, ob ein Programm bei einer Eingabe anhält | |
| Rechenaufwand | wie viele Schritte ein Verfahren für eine Eingabe braucht | |
| Exponentiell | der Aufwand verdoppelt sich mit jedem weiteren Element | 2 hoch n |
| Brute Force | alle Möglichkeiten der Reihe nach ausprobieren |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Manche Fragen kann ein Programm immer beantworten
Eine Frage ist entscheidbar, wenn ein Programm sie für jede Eingabe richtig mit ja oder nein beantwortet und dabei immer anhält.
Ob eine Zahl gerade ist, ob ein Wort zu einem Muster passt, ob Klammern stimmen: alles entscheidbar. Auch ob ein Programm einen Syntaxfehler hat, denn der Compiler liest es dazu nur einmal durch.
Das Halteproblem ist unentscheidbar
Das Halteproblem fragt: Hält das Programm P bei der Eingabe E an? Alan Turing zeigte 1936, dass kein Programm das für alle P und E richtig sagen kann.
Das liegt nicht an zu wenig Speicher oder Zeit. Die Frage selbst führt zu einem Widerspruch, wenn es ein solches Werkzeug gäbe.
Die Beweisidee als Programm
def haelt(programm, eingabe):
# Angenommen, es gaebe diese Funktion. Sie antwortet True oder False.
...
def gegenteil(programm):
if haelt(programm, programm):
while True:
pass # laeuft ewig
return "fertig" # haelt sofort
# Was geschieht bei gegenteil(gegenteil)?Warum gegenteil(gegenteil) nicht gehen kann
| Angenommen, haelt sagt | Dann tut gegenteil(gegenteil) | Das ist ein Widerspruch, weil |
|---|---|---|
| True (hält an) | läuft ewig | es nicht angehalten hat |
| False (hält nicht) | gibt fertig zurück | es angehalten hat |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein häufiger Fehler
Warnung
Viele denken, unentscheidbar heiße „für jedes Programm unmöglich“. Das stimmt nicht. Für viele einzelne Programme lässt sich das Halten sehr wohl zeigen. Es gibt nur kein einziges Verfahren, das es für alle Programme richtig sagt.
Entscheidbar heißt nicht schnell
Selbst bei entscheidbaren Fragen kann die Antwort zu lange dauern. Beim Teilsummen-Problem sucht man aus n Zahlen eine Auswahl mit einer bestimmten Summe. Der einfache Weg probiert alle Teilmengen aus (Brute Force).
Bei n Zahlen sind das 2 hoch n Teilmengen. Jede weitere Zahl verdoppelt die Arbeit: Das heißt exponentiell.
Arbeit bei einer Milliarde Prüfungen je Sekunde
| Zahlen n | Teilmengen 2 hoch n | Dauer | Zum Vergleich n mal n |
|---|---|---|---|
| 10 | 1024 | ein Wimpernschlag | 100 |
| 30 | rund 1,07 Milliarden | etwa 1 Sekunde | 900 |
| 40 | rund 1,1 Billionen | etwa 18 Minuten | 1600 |
| 50 | rund 1,1 Billiarden | etwa 13 Tage | 2500 |
| 60 | rund 1,15 Trillionen | etwa 36 Jahre | 3600 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Alle Teilmengen einer Rechnungsliste
# Teilsummen-Problem: Gibt es Rechnungen, die zusammen genau 100 Euro ergeben?
rechnungen = [30, 45, 25, 60, 15]
ziel = 100
n = len(rechnungen)
versuche = 0
gefunden = []
for maske in range(2 ** n):
versuche = versuche + 1
summe = 0
auswahl = []
for i in range(n):
# Das i-te Bit der Zahl maske sagt, ob Rechnung i dabei ist.
if (maske // (2 ** i)) % 2 == 1:
summe = summe + rechnungen[i]
auswahl.append(rechnungen[i])
if summe == ziel and gefunden == []:
gefunden = auswahl
print("Versuche:", versuche)
print("Erste Auswahl mit 100 Euro:", gefunden)
# Fuegen Sie eine sechste Rechnung hinzu und beobachten Sie die Versuche.
Prüfen ist leicht, Finden ist schwer
Bei der Teilsumme ist eine Lösung leicht zu prüfen: Sie addieren die gewählten Zahlen und vergleichen mit dem Ziel. Das Finden ist dagegen ohne Trick nur durch Probieren bekannt.
Solche Probleme heißen NP. Ob es doch einen schnellen Weg zum Finden gibt, ist die größte offene Frage der Informatik. Wer sie beantwortet, bekommt eine Million Dollar.
Teilmengen bei zwanzig Zahlen
python3 -c "print(2 ** 20)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Teilmengen bei vierundsechzig Zahlen
python3 -c "print(2 ** 64)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Minuten bei 2 hoch 40 Schritten
python3 -c "print(2 ** 40 // 10 ** 9 // 60)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Eine Teilsumme zu 15 suchen
python3 -c "from itertools import combinations as c; print([s for k in range(6) for s in c([3,5,7,11,13],k) if sum(s)==15])"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Weiterführend
Erweitern Sie finde_teilmenge so, dass es auch zählt, wie viele Teilmengen es geprüft hat. Rechnen Sie aus, wie viele es bei 25 Zahlen im schlechtesten Fall sind.
Erklären Sie dann in zwei Sätzen, warum ein doppelt so schneller Rechner bei dieser Methode nur eine einzige Zahl mehr erlaubt.