ahodges/Turing.html
nachsehen.
In diesem Kapitel wird das Konzept der Turing-Maschine
vorgestellt. Eine solche Maschine ist eine exakte Präzisierung
des Begriffs Algorithmus , den wir bisher eher intuitiv
verwendet haben.
Jede berechenbare Funktion
kann durch eine Turing-Maschine implementiert werden. Umgekehrt stellt jede Turing-Maschine
eine berechenbare Funktion dar.
Eine Turing-Maschine ist wesentlich leistungsfähiger als ein Kellerautomat , da sie
nicht der Einschränkung unterliegt, immer nur das oberste Symbol lesen
oder manipulieren zu können.
Turing-Maschinen wurden von Alan Turing 1936
eingeführt - also vor Beginn des Computerzeitalters. Turing war
im 2. Weltkrieg maßgeblich an der Entschlüsselung des
Enigma-Codes der Wehrmacht beteiligt - er war somit
keineswegs ein weltfremder Theoretiker. Seine interessante Biographie
findet man in [4].
Im WWW sollte man unter www.wadham.ox.ac.uk/ ahodges/Turing.html
nachsehen.
Prof. Dr. Reinhard Völler