Turingmaschine
"Biber am laufenden Band"
Autor(en): Georg Weuffen - Oktober2019
Kapitelübersicht
Hier muss man sich zwischen Theorie und Praxis entscheiden
Die Bestandteile und Funktionsweise der Turingmaschine werden erklärt und das Simulations- programm vorgestellt und gestartet
Als Übung entwickeln wir ein Additions- und ein Sortierprogramm
Das Halteproblem, das Entscheidungs- problem die Churchsche These und Berechenbarkeit werden thematisiert
Die Busy-Beaver-Funktion, eine Ideensammlung zum Weiterarbeiten und Literaturtipps
Inhalt
Dieses Modul stellt ein umfangreiches und leistungsfähiges Simulationsprogramm bereit.
Die Theoretische Informatik im Allgemeinen und die Turingmaschine im Besonderen werden nur selten im Informatikunterricht behandelt. Das Ziel dieses Moduls ist, die grundlegenden Begriffe der Theoretischen Informatik anschaulich zu vermitteln und die Arbeitsweise der Turingmaschine zu erläutern.
Es werden folgende Themen behandelt:
Halteproblem
Entscheidungsproblem
Churchsche These
Berechenbarkeit
Arbeits- und Funktionsweise der Turingmaschine
Bedeutung der Turingmaschine für die Informatik
Das Problem der fleißigen Biber
Glossar