TURING-MASCHINE

Máquinas de Turing

(Recop.) Justo Fernández López

 

Vgl.:

Algorithmus / Rekursivität

 

Turing-Maschine. Von A. M. Turing entworfenes (und nach ihm benanntes) Gedankenmodell einer universellen Rechenmaschine mit einem unendliche großen Speicher. T. werden wegen ihrer technischen Aufwendigkeit nicht materiell realisiert, sie dienen der exakten Definition wichtiger mathematisch-logischer Grundbegriffe wie Algorithmus, rekursive Funktion. Hinsichtlich der Äquivalenz zwischen Automaten und Grammatiken von natürlichen Sprachen entspricht die T. der schwachen Generativen Kapazität, da sie eine rekursiv aufzählbare Menge von Ketten (Sätzen) zu erzeugen vermag.“ [Bußmann, S. 811]

Die universelle Turing-Maschine. Die Grundidee ist folgende: Man codiert die Liste von Befehlen für eine beliebige Turing-Maschine T als Folge von 0- und 1-Zeichen, die sich auf einem Band darstellen lässt. Dieses Band verwendet man dann als ersten Teil des Inputs für eine spezielle Maschine U, eine so genante universelle Turing-Maschine; sie bearbeitet den restlichen Input in derselben Weise wie T. Die universelle Turing-Maschine ist ein universeller Imitator. Die erste Teil des Bands liefert der universellen Turingmaschine U die vollständige Information, die sie benötigt, um jede vorgegebene Maschine T exakt zu imitieren!“  

[Pernrose, Roger: Computerdenken. Des Kaisers neue Kleide oder Die Debatte um Künstliche Intelligenz, Bewusstsein und die Gesetze der Physik. Heidelberg: Spektrum der Wissenschaft, 1991, S. 48]

„Alle modernen, vielseitig verwendbaren Computer sind letztlich universelle Turing-Maschinen“.

[Pernrose, Roger: Computerdenken. Des Kaisers neue Kleide oder Die Debatte um Künstliche Intelligenz, Bewusstsein und die Gesetze der Physik. Heidelberg: Spektrum der Wissenschaft, 1991, S. 54]