Turingmaschine als Berechnungsmodell

Worum geht es hier?

Um Fragen zur algorithmischen Lösbarkeit von Problemen zu klären, muss vorab präzisiert werden, was man unter "algorithmisch lösbar" versteht. Das führt letztlich zur Schwierigkeit, das "Wesentliche" eines von einem Rechner ausführbaren Verfahrens mit möglichst konkreten Beschreibungsmitteln zu erfassen.

Wir schlagen hier den Weg von Alan Turing ein, der ein Maschinenmodell zur automatisierten Ausführung von algorithmischen Problemlösungen entwickelt hat, das automatisierte Verarbeitung mit möglichst einfachen Mitteln realisiert.

Zur Verdeutlichung seines Maschinenmodells benutzen wir die Kara-Simulationsprogramme (siehe Kara).

Hier lernst du ...

• ... was eine Turingmaschine ist.
• ... wie man algorithmische Berechenbarkeit mit einer Turingmaschine präzisiert.
• ... inwieweit eine Turingmaschine als programmierbares System angesehen werden kann.