Dieses Übungsheft für den Informatikunterricht der Oberstufe bietet eine fundierte und systematische Einführung in die theoretische Informatik. Das Material verknüpft abstrakte mathematische Konzepte mit anschaulichen Erklärungen und führt die Lernenden Schritt für Schritt von der Funktionsweise der Turingmaschine bis hin zum Beweis der Unentscheidbarkeit des Halteproblems.

Inhaltliche Schwerpunkte:

• Turingmaschine (TM):Formale Definition, Aufbau (Band, Lese-/Schreibkopf, Zustände) sowie Konfiguration und Übergänge.

• Funktionsweise:Systematische Konstruktion und Schritt-für-Schritt-Analyse (Tracing) einer Turingmaschine für kontextsensitive Sprachen (Beispiel: L = aⁿbⁿ) sowie eine Betrachtung der Universellen Turingmaschine.

• Theoretische Grenzen:Erklärung der Church-Turing-These, Einordnung in die Chomsky-Hierarchie und die Unterscheidung von Begriffen wie berechenbar, entscheidbar und (semi-)entscheidbar / rekursiv aufzählbar.

• Unentscheidbarkeit:Anschaulicher und schrittweiser Beweis der Unentscheidbarkeit des Halteproblems (inklusive Vorbereitung durch das Cantor'sche Diagonalverfahren und Selbstbezug).

• Weiterführende Konzepte:Einführung in die Problem-Reduktion, den Satz von Rice und einen Ausblick auf die Komplexitätstheorie.

Aufbau und didaktische Struktur:

• Theorie und Anwendung:Jedes Kapitel kombiniert wissenschaftlich fundierte Erklärungen mit direkt darauffolgenden Übungs- und Reflexionsaufgaben.

• Integrierte Differenzierung:Die Aufgabenstellungen sind durch ein transparentes Sterne-System in drei Anforderungsbereiche (leicht, mittel, schwer) unterteilt, um unterschiedlichen Leistungsniveaus gerecht zu werden.

• Zusatzmaterialien:Ein kompaktes Fachglossar klärt zentrale Begrifflichkeiten. Ein ausführlicher Lösungsteil mit detaillierten Erklärungen ermöglicht eine zuverlässige und unkomplizierte (Selbst-)Kontrolle.

Einsatzmöglichkeiten im Unterricht:Das modular aufgebaute Material ist ideal für die theoretische Informatik im Leistungskurs oder vertiefenden Grundkurs (Klasse 11-13). Da für die Bearbeitung lediglich Stift und Papier benötigt werden („Unplugged“), lässt es sich flexibel im regulären Fachunterricht, in konzentrierten Erarbeitungsphasen oder zur strukturierten Klausur- und Abiturvorbereitung einsetzen. Die optionalen Programmier-Referenzen bieten zudem eine Brücke in die angewandte Informatik.