• Increase font size
  • Default font size
  • Decrease font size

Turingmaschine

E-Mail Drucken PDF

     Alan M. Turing ( 1926 -1954)

Die Zugehörigkeit eines Wortes zu einer Sprache, deren Grammatik nach Chomsky Typ 0 entspricht kann über eine Turingmaschine erfolgen. Die Turingmaschine hat aber einen weitaus größeren Anwendungsbereich.

1936 wurde durch Alan Turing das Modell einer Rechenmaschine vorgestellt. Mit ihr sollte es möglich sein, ausgehend von einer einfachen Konzeption, alles zu berechnen, was berechenbar ist bzw. wofür eine Lösungsstrategie existiert     Churchsche These .

Damit hatte die Turingmaschine die gleiche Funktionalität wie der komplizierteste Computer der Welt. Darüber hinaus ist das Konzept der Turingmaschine denkbar einfach.

Konzept der Turingmaschine


Ein beliebig langes Band wird mit Symbolen gefüllt, die einem Bandalphabet entstammen (z.B. a oder b, 1 oder 0). Ein Schreib -und Leseknopf hat die Aufgabe, ein Zeichen vom Band zu lesen (input) oder ein Zeichen auf das Band zu schreiben (output). Der Schreib- bzw. Leseknopf kann bei den meisten Modellen  3  `Bewegungen `ausführen, 1 Schritt nach rechts (R), ein Schritt nach links (L), Stop (S).

Die jeweilige Bewegung kann zu einem Zustandübergang führen.

Insgesamt kann die Turingmaschine ausgehend von einem definierten Startzustand unendlich viele innere Zustände annehmen.Die Programmierung der Maschine erfolgt im Kontext des zu beschreibenden Problems durch eine Menge an vorgegebenen Regeln. Diese Regeln haben einen vorgegebenen Aufbau der Form (Zustand, Input -- Output, Bewegung, Neuzustand )

Beispiel : Fleißige Biber

Eines der bekanntesten Beispiele für die Anwendung der Turingmaschine ist das durch Tibor Rado aufgestellte Problem der später so genannten Fleißigen Biber. Es handelt sich hierbei um eine Funktion die einer festen Anzahl von inneren Zuständen eine Menge von Einsen zuordnet, welche eine stoppende Turingmaschine auf ein leeres Band schreiben.

Die Turingmaschine wird für dieses Beispiel durch ein Pythonprogramm simuliert. Der Grad der inneren Ordnung, d. h. die Anzahl n der inneren Zustände beträgt 2. Um die Übersichtlichkeit zu erhalten, handelt es sich um ein reines Konsolenprogramm. Eine Sicht kann jederzeit auf die Fachklasse aufgesetzt werden, da die Turingmaschine als Objekt implementiert wurde.

   Source 

Aktualisiert ( Donnerstag, 26. November 2009 um 17:04 Uhr )  

(c) g-ymnasium.de 2006 - 2013 + Administrator