Turingmaschine.com
 Alan Turing und seine Turingmaschine

Header

 

Die Turingmaschine

Die Turingmaschine ist ein mathematisches Modell des britischen Mathematikers Alan Turing. Er entwarf dieses 1936 auf Grundlage des  von David Hilbert im Jahr 1920 formulierten Hilbertprogramms. Im Grunde versucht die Turingmaschine ein Modell des mathematisch arbeitenden Menschen zu schaffen, genauer, es versucht berechenbare Funktionen in Klassen zu gruppieren.

Die Turingmaschine ist eins der grundlegenden Modelle der Informatik ohne die heute kein PC oder Programm funktionieren könnte. Es kommt mit nur 3 Operationen aus: Lesen, Schreiben und Lese-Schreibe-Kopf bewegen aus. Faszinierend, denn aus diesen 3 Operationen lassen sich alle Grundfunktionen der heutigen Mathematik, wie Addieren, Subtrahieren und Multiplizieren ableiten bzw. simulieren. Mit diesem Fundament lassen sich dann auch sehr komplexe Funktionen und Rechenoperationen durchführen. Das bildet die Basis der der heutigen computergestützten Programme. Eine Funktion die sich mit dem Modell der Turingmaschine darstellen lässt nennt man eine turingberechenbare Funktion.

Eine sehr interessante These zur Turingmaschine ist die Church-Turing-These, welche von Alonzo Church und Alan Turing aufgestellt wurde und auch Churchsche These genannt wird. Diese These behauptet, dass alle von Menschen berechenbaren mathematischen Funktionen durch eine Turingmaschine gelöst werden können. Was implizit nicht bedeutet, dass alle Funktionen gelöst werden können. Die Funktionen die der Mensch nicht lösen kann, kann auch eine Turingmaschine nicht lösen. Ein Beispiel für so eine mathematische Funktion die ein Mensch nicht lösen kann ist das Halteproblem der Informatik.

Der Aufbau einer Turingmaschine ist ein unendliches langes Schreibband, das sequentiell Felder hat die von einem Schreib-Lese-Kopf beschrieben werden können.