Folie 42 / 65
Informatik in der Schule - Ja, aber wie?
1. Tag des Informatikunterrichts, Universität Saarbrücken, 06.03.2019
"Die theoretische Informatik beschäftigt sich erstens mit Logik,
zweitens mit der Theorie formaler Sprachen und drittens mithilfe
der Automatentheorie mit den grundsätzlichen Fragen, wie
aufwendig Berechnungen sind und wo die Grenze der Berechenbarkeit
liegt. Ja, es existieren tatsächlich viele exakt beschreibbare
Probleme, die kein Computer dieser Welt wird lösen können,
egal wie schnell er ist. So gibt es beispielsweise kein Programm,
das entscheiden kann, ob ein beliebiges anderes Computerprogramm
je zu einem Ende kommen wird. Allgemeiner formuliert,
kann kein Programm beliebige andere Programme daraufhin
überprüfen, ob sie tatsächlich das Gewünschte und nichts anderes
tun. Diese als Halteproblem bekannte Erkenntnis ist
mit der Nichtexistenz eines Perpetuum mobile in der Physik vergleichbar.
Der britische Mathematiker Alan Turing hat 1936
solche Überlegungen mit einem Gedankenmodell eines Computers
angestellt, der nur aus einem endlos langen Papierband besteht,
das von einem Lese-/ Schreibkopf nach fixen Regeln gelesen
und wieder beschrieben wird. Die theoretische Informatik
konnte beweisen, dass kein anderer Computer ein Problem
wird lösen können, welches für eine sogenannte Turingmaschine
unlösbar ist.
Wer sich für solche theoretischen und
philosophischen Überlegungen begeistern kann, wird sich über
die Bücher Das Affenpuzzle ( dünn ) von David Harel und
Gödel – Escher – Bach ( dick ) von Douglas Hofstadter freuen.
Insbesondere bei Letzterem dürften auch Freunde der Linguistik
auf ihre Kosten kommen, da formale Sprachen und Grammatiken
ebenfalls zu den Themen der theoretischen Informatik gehören."
