Grenzen der Berechenbarkeit

Dieser Lernbereich handelt von Grenzen – und zwar von zwei verschiedenen.

Die erste ist eine Grenze der Praxis: Ein Problem ist lösbar, aber die Lösung dauert zu lange. Bei einem Sortierverfahren ist das ärgerlich; bei einem Passwort ist es genau das, was wir wollen. Dieselbe Rechnung, zwei Bewertungen.

Die zweite ist eine Grenze des Prinzips: Es gibt Fragen, die kein Algorithmus beantworten kann – gleich wie schnell der Rechner ist und wie groß das Modell. Das Halteproblem ist die berühmteste davon, und Alan Turing hat sie 1936 entschieden, neun Jahre bevor der erste Universalrechner lief.

Laufzeit messen

Eine Zeitmessung in Sekunden misst den Rechner mit: Taktfrequenz, Cache, Programmiersprache, andere Programme. Dasselbe Programm mit denselben Daten kann auf zwei Geräten um den Faktor 5 auseinanderliegen.

Deshalb zählt man stattdessen die zeitkritische Anweisung – diejenige Anweisung, die am häufigsten ausgeführt wird und deren Anzahl mit der Eingabegröße wächst. Bei Sortierverfahren ist das der Vergleich zweier Schlüssel. Diese Zahl ist auf jedem Gerät dieselbe.

Drei Fälle

• Best Case – die günstigste Eingabe, z. B. eine bereits sortierte Liste
• Worst Case – die ungünstigste Eingabe, z. B. genau falsch herum sortiert
• Average Case – der Durchschnitt über alle möglichen Eingaben

In der Praxis nennt man meist den Worst Case, denn er ist eine Zusage: schlimmer wird es nicht. Der Average Case ist ehrlicher, aber schwer zu bestimmen – man muss über alle Eingaben mitteln.

Sortierverfahren

Man unterscheidet zunächst danach, ob überhaupt verglichen wird:

• vergleichsbasiert – Bubble-, Selection-, Insertion-, Merge-, Quick-, Heapsort
• nicht vergleichsbasiert – Radix-, Counting-, Bucketsort; sie nutzen die Struktur der Schlüssel (z. B. ihre Ziffern) statt zu vergleichen

Stabilität

Ein Verfahren heißt stabil, wenn Datensätze mit gleichem Sortierschlüssel ihre bisherige Reihenfolge behalten. Beide Ergebnisse sind korrekt sortiert – Stabilität ist eine Zusatzgarantie, keine Frage von richtig oder falsch. Gebraucht wird sie, sobald man mehrfach hintereinander sortiert: erst nach Nachname, dann nach Abteilung.

In-place

In-place heißt: Der zusätzliche Speicherbedarf hängt nicht von der Datenmenge ab, er ist O(1). Mergesort ist out-of-place, weil er die Hälften zwischenspeichern muss. Achtung bei rekursiven Verfahren: Auch der Aufrufstapel ist Speicher – Quicksort belegt O(log n), im Worst Case O(n).

Die untere Schranke

Ein vergleichsbasiertes Verfahren braucht mindestens O(n·log n) Vergleiche. Der Grund: Jeder Vergleich liefert höchstens ein Bit Information, und es gibt n! mögliche Anordnungen. Radixsort unterschreitet diese Schranke nicht – sie gilt für ihn schlicht nicht, weil er mehr über die Daten weiß als nur „größer oder kleiner".

Bubblesort an einem Beispiel

Feld: 5 2 9 1

Nach dem ersten Durchgang steht die 9 endgültig rechts – das gilt in jedem Durchgang für das größte noch unsortierte Element. Ein vierter Durchgang würde ohne Tausch bleiben; der Merker beendet das Verfahren.

Zusammen: 6 Vergleiche, 3 Tausche (also 6 Bewegungen).

Komplexitätsklassen

Die O-Schreibweise (nach Edmund Landau) beschreibt, wie der Aufwand wächst, wenn die Eingabe wächst – nicht, wie viele Sekunden er dauert. Konstante Faktoren und langsamer wachsende Summanden fallen weg: Aus 3n² + 5n + 200 wird O(n²).

Die Klasse sagt nichts über kleine Eingaben. Ein Verfahren mit 100·n Schritten ist für n = 50 langsamer als eines mit n² Schritten – der Wechsel liegt erst bei n = 100. Genau deshalb sortieren reale Bibliotheken kurze Abschnitte mit Insertionsort, obwohl er die schlechtere Klasse hat.

Brute-Force

Brute-Force heißt: alle Möglichkeiten der Reihe nach durchprobieren. Das Verfahren findet die Lösung garantiert – die Frage ist nur, wann.

Bei einem Zeichenvorrat von z Zeichen gibt es zⁿ Passwörter der Länge n. Jedes zusätzliche Zeichen multipliziert die Anzahl mit z; das ist exponentielles Wachstum.

Diese Rechnung gilt allerdings nur für zufällige Passwörter. Reale Angriffe probieren zuerst die wahrscheinlichen: Wörterbuchangriffe testen bekannte Muster wie Wort + Jahreszahl + Ausrufezeichen, lange bevor sie systematisch alle Zeichenketten durchgehen.

Hier kippt die Bewertung des ganzen Lernbereichs: Ein hoher Laufzeitaufwand war bisher ein Mangel – jetzt ist er der Schutz. Passwortverfahren wie bcrypt rechnen deshalb absichtlich langsam.

Das Halteproblem

Gibt es einen Algorithmus, der für jedes Programm P und jede Eingabe E entscheidet, ob P bei E nach endlich vielen Schritten anhält?

Für einzelne Programme lässt sich die Frage oft beantworten. Gesucht ist ein Verfahren, das es für alle tut. Ein solches Verfahren gibt es nicht – und das lässt sich beweisen.

Der Widerspruchsbeweis

Ein Widerspruchsbeweis zeigt eine Aussage, indem er ihr Gegenteil annimmt und daraus etwas Unmögliches folgert. Sie kennen ihn aus der Mathematik vom Beweis, dass √2 keine Bruchzahl ist.

1. Gegenannahme. Es gebe ein Programm haelt(P, E), das für jedes Programm und jede Eingabe entscheidet, ob P bei E anhält – und das dabei selbst immer anhält.

2. Der Gegenspieler. Aus haelt bauen wir ein Programm seltsam:

   boolean seltsam(String p) {
       if (haelt(p, p)) {
           while (true) { }   // hält absichtlich NICHT an
       }
       return true;           // hält an
   }
   

   seltsam fragt, ob das übergebene Programm mit sich selbst als Eingabe anhält – und tut dann das Gegenteil der Auskunft. Ein Programm als Eingabe eines Programms ist nichts Ungewöhnliches: Quelltext ist Text, und ein Compiler bekommt täglich Programme als Eingabe.

3. Die Fallunterscheidung. Wir rufen seltsam mit seinem eigenen Quelltext auf.

   • Sagt haelt, es halte an, geht seltsam in die Endlosschleife – es hält also nicht an.
   • Sagt haelt, es halte nicht an, gibt seltsam sofort true zurück – es hält also doch an.

   In beiden Fällen ist die Auskunft falsch, obwohl haelt laut Annahme immer richtig antwortet.

4. Der Schluss. An seltsam ist nichts unzulässig – es benutzt nur eine Verzweigung und eine Schleife. Falsch sein kann daher nur die Gegenannahme: Ein Programm haelt mit den geforderten Eigenschaften existiert nicht.

Der Beweis handelt von Logik, nicht von Rechenleistung. Er gilt für jedes Verfahren, das sich als Programm aufschreiben lässt – auch für ein neuronales Netz beliebiger Größe. Mehr Rechenzeit verschiebt die Grenze des Machbaren, nicht die des Berechenbaren.

• Beurteilt wird ein Algorithmus durch Zählen der zeitkritischen Anweisung, nicht durch Stoppen der Sekunden.
• Vergleiche und Bewegungen werden getrennt gezählt – erst dann sieht man den Unterschied zwischen den Verfahren.
• Best, Average, Worst Case hängen von der Eingabe ab; genannt wird meist der Worst Case, weil er eine Garantie ist.
• Vergleichsbasierte Verfahren kommen nicht unter O(n·log n); Radixsort umgeht die Schranke, weil er die Struktur der Schlüssel nutzt.
• Quicksort ist im Mittel am schnellsten, hat aber einen Worst Case von O(n²) – bei ungünstiger Pivotwahl, etwa bei bereits sortierten Daten.
• Exponentielles Wachstum macht Brute-Force unwirtschaftlich; bei Passwörtern ist genau das der Schutz.
• Das Halteproblem ist nicht algorithmisch lösbar. Das ist keine Frage der Rechenleistung, sondern ein bewiesenes Ergebnis.