Turingmaschine

Eine Turingmaschine ist ein mathematisches Modell der theoretischen Informatik, das eine abstrakte Maschine definiert. Bei diesem Rechnermodell werden nach festgelegten Regeln Manipulationen von Zeichen vorgenommen. Die Turingmaschine ist benannt nach dem britischen Mathematiker Alan Turing, der sie 1936/37 einführte.

Turingmaschinen machen die Begriffe des Algorithmus und der Berechenbarkeit mathematisch fassbar, das heißt, sie formalisieren diese Begriffe. Im Gegensatz zu einem physischen Computer ist eine Turingmaschine damit ein mathematisches Objekt und kann mit mathematischen Methoden untersucht werden.

Eine Turingmaschine repräsentiert einen Algorithmus bzw. ein Programm. Eine Berechnung besteht dabei aus schrittweisen Manipulationen von Symbolen bzw. Zeichen, die nach bestimmten Regeln auf ein Speicherband geschrieben und auch von dort gelesen werden. Ketten dieser Symbole können verschieden interpretiert werden, unter anderem als Zahlen. Damit beschreibt eine Turingmaschine eine Funktion, welche Zeichenketten, die anfangs auf dem Band stehen, auf Zeichenketten, die nach „Bearbeitung“ durch die Maschine auf dem Band stehen, abbildet. Eine Funktion, die anhand einer Turingmaschine berechnet werden kann, wird Turing-berechenbar oder auch einfach berechenbar genannt.

Turingmaschinen spielen auch eine bedeutende Rolle bei der Akzeptanz von formalen Sprachen. So entsprechen die Sprachen, die von Turingmaschinen akzeptiert werden, den mit Typ-0-Grammatiken definierbaren Sprachen. Es konnte gezeigt werden, dass eine Transformationsgrammatik der Grammatik einer Turingmaschine entsprechen kann, die in der Lage ist, jede berechenbare Funktion zu berechnen.^[1] Eine Sprache oder ein Computersystem heißen Turing-vollständig, wenn sie beziehungsweise es alle Operationen ausführen kann, die eine universelle Turingmaschine ausführen kann.

1. ↑ George A. Miller: Wörter. Streifzüge durch die Psycholinguistik. Herausgegeben und aus dem Amerikanischen übersetzt von Joachim Grabowski und Christiane Fellbaum. Spektrum der Wissenschaft, Heidelberg 1993; Lizenzausgabe: Zweitausendeins, Frankfurt am Main 1995; 2. Auflage ebenda 1996, ISBN 3-86150-115-5, S. 255.