Turing-Maschinen
Erste Folie Zurück Vorwärts Letzte Folie

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."

Quelle: Beat Döbeli Honegger (2016) Mehr als 0 und 1 - Schule in einer digitalisierten Welt. Bern: hep Verlag.
Biblionetz-Verweise: