Informatik · Klasse 13

Ideen für aktives Lernen

Das Halteproblem und Unentscheidbarkeit

Aktive Auseinandersetzung mit dem Halteproblem zeigt Schülerinnen und Schülern, warum theoretische Informatik nicht nur abstrakt bleibt, sondern ihr eigenes Programmverhalten prägt. Durch das Nachvollziehen von Turings Argumentation in Partner- und Gruppenarbeit wird die Unentscheidbarkeit greifbar, weil sie selbst die Grenzen von Simulationen erleben.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Algorithmen
• KMK: Sekundarstufe II - Informatik, Mensch und Gesellschaft

• 20–50 Min.
• Partnerarbeit → Ganze Klasse
• 4 Aktivitäten

Aktivität 01

• Sokratisches Seminar
• 30 Min. · Partnerarbeit

Paararbeit: Einfache Halteproblem-Beispiele

Paare erhalten Vorlagen für rekursive Programme, die potenziell nicht halten. Sie testen Eingaben manuell und mit Debuggern, protokollieren Ergebnisse und diskutieren, warum eine allgemeine Entscheidung fehlschlägt. Abschließend teilen sie Beispiele im Plenum.

Erklären Sie, warum das Halteproblem unentscheidbar ist.

Moderationstipp

Lassen Sie die Schülerinnen und Schüler während der Paararbeit bewusst Programme entwerfen, die nur unter bestimmten Bedingungen halten, um den Unterschied zu polynomialen Problemen zu verdeutlichen.

Worauf zu achten ist

Stellen Sie die Frage: 'Wenn wir nicht beweisen können, ob jedes Programm anhält, welche Konsequenzen hat das für die Entwicklung von Software, die niemals abstürzen darf?' Lassen Sie die Schüler in Kleingruppen diskutieren und die wichtigsten Punkte sammeln.

• Analysieren
• Bewerten
• Erschaffen
• Sozialbewusstsein
• Beziehungsfähigkeit

Aktivität 02

• Sokratisches Seminar
• 45 Min. · Kleingruppen

Small Groups: Reduktionsbeweis nachstellen

Gruppen von vier gliedern Turings Beweis in Schritte auf: Annahme eines Halteprogramms H, Konstruktion des kontradiktorischen Programms D und Ausführung auf sich selbst. Jede Gruppe simuliert mit Pseudocode und präsentiert den Widerspruch.

Analysieren Sie die Auswirkungen der Unentscheidbarkeit auf die Softwareentwicklung.

Moderationstipp

Führen Sie den Reduktionsbeweis im Plenum schrittweise vor, indem die Gruppen jeweils einen Teil des Selbstbezugsparadoxons oder Diagonalarguments präsentieren.

Worauf zu achten ist

Geben Sie den Schülern eine kurze Beschreibung eines hypothetischen 'Programm-Checker'-Programms. Bitten Sie sie, zwei Sätze zu schreiben, die erklären, warum ein solches Programm, das für *alle* Programme und Eingaben funktioniert, nicht existieren kann, basierend auf dem Halteproblem.

• Analysieren
• Bewerten
• Erschaffen
• Sozialbewusstsein
• Beziehungsfähigkeit

Aktivität 03

• Sokratisches Seminar
• 50 Min. · Ganze Klasse

Whole Class: Debatte zu Verifikationsgrenzen

Die Klasse teilt sich in Pro- und Contra-Teams: Automatische Verifikation vollständig möglich oder grundsätzlich begrenzt? Jede Seite bereitet Argumente mit Beispielen vor, moderiert durch den Lehrer, mit Abstimmung am Ende.

Bewerten Sie die Grenzen der automatischen Programmverifikation.

Moderationstipp

Moderieren Sie die Debatte mit klaren Rollen (z.B. Entwicklerin, Sicherheitsingenieurin), damit die Argumente strukturiert bleiben und nicht ins Abstrakte abgleiten.

Worauf zu achten ist

Jeder Schüler erhält eine Karte mit der Aufgabe: 'Beschreiben Sie in einem Satz, was das Halteproblem ist, und in einem weiteren Satz, warum es unentscheidbar ist. Nennen Sie ein Beispiel für eine praktische Auswirkung dieser Unentscheidbarkeit.'

• Analysieren
• Bewerten
• Erschaffen
• Sozialbewusstsein
• Beziehungsfähigkeit

Aktivität 04

• Sokratisches Seminar
• 20 Min. · Einzelarbeit

Individual: Persönliche Unentscheidbarkeits-Reflexion

Jeder Schüler entwirft ein eigenes Programm, das das Halteproblem illustriert, und schreibt eine kurze Analyse der Unentscheidbarkeit. Im Anschluss peer-review in lockeren Runden.

Erklären Sie, warum das Halteproblem unentscheidbar ist.

Worauf zu achten ist

Stellen Sie die Frage: 'Wenn wir nicht beweisen können, ob jedes Programm anhält, welche Konsequenzen hat das für die Entwicklung von Software, die niemals abstürzen darf?' Lassen Sie die Schüler in Kleingruppen diskutieren und die wichtigsten Punkte sammeln.

• Analysieren
• Bewerten
• Erschaffen
• Sozialbewusstsein
• Beziehungsfähigkeit

Einige Hinweise zum Unterrichten dieser Einheit

Erfahrene Lehrkräfte beginnen mit konkreten, fehlerhaften Programmen aus dem Unterricht, die entweder halten oder nicht, um die Frage nach der Vorhersagbarkeit aufzuwerfen. Vermeiden Sie es, das Halteproblem sofort mit formalen Beweisen zu beginnen, da dies die Motivation senkt. Stattdessen nutzen Sie die Intuition der Lernenden über Abbrüche und Endlosschleifen, bevor Sie die theoretische Tiefe erschließen.

Erfolgreiches Lernen zeigt sich darin, dass die Schülerinnen und Schüler das Halteproblem nicht nur definieren, sondern in eigenen Worten erklären können, warum keine universelle Lösung existiert. Sie erkennen konkrete Auswirkungen auf Softwareentwicklung und können Beispiele für partielle Lösungen nennen.

---

Vorsicht vor diesen Fehlvorstellungen

• Während der Paararbeit zur Simulation einfacher Halteproblem-Beispiele könnte die Aussage auftauchen: 'Wenn wir nur genug Programme testen, finden wir irgendwann ein Muster.'

  Fragen Sie die Lernenden konkret: 'Wie viele Programme müssten Sie testen, um sicher zu sein, dass es kein Gegenbeispiel gibt?' und verweisen Sie auf die Unendlichkeit möglicher Eingaben.

• Im Reduktionsbeweis könnte die Fehlvorstellung entstehen: 'Unentscheidbarkeit bedeutet, dass Programme immer abstürzen.'

  Lenken Sie die Aufmerksamkeit auf die Materialien zur Gruppendiskussion: 'Zeigen Sie anhand der Tools wie Timeouts, dass partielle Lösungen existieren, die zwar nicht universell sind, aber in der Praxis funktionieren.'

• In der Debatte zu Verifikationsgrenzen könnte geäußert werden: 'Das Halteproblem ist nur eine theoretische Spielerei ohne Bedeutung für die echte Softwareentwicklung.'

  Fordern Sie die Schüler auf, ihre Argumente mit den Debattenrollen zu verknüpfen: 'Nennen Sie konkrete Beispiele aus Compilerbau oder KI, die von den Grenzen des Halteproblems betroffen sind.'

---

In dieser Übersicht verwendete Methoden

• Sokratisches Seminar