Turingmaschine
Aus InfWiki
Die von dem Mathematiker Alan Turing entwickelte Turingmaschine liefert ein Modell zur Elektronischen Ausführung von Algorithmen. Sie erlaubt die Implementierung jeder berechenbaren mathematischen Funktion.
Inhaltsverzeichnis |
Funktionsweise
Eine Turingmaschine besteht aus einem einfachen Band, auf dem Daten gespeichert werden können, sowie einem Lese- und Schreibkopf, der sich über dem Band bewegt. Die einzigen Befehle, die diese Maschine ausführen kann sind somit Lesen, Schreiben und die Verschiebung des Lese- und Schreibkopfes.
Programmiersprache
Die Befehle, die zu Programmierung der Turingmaschine verwendet werden, sind nach folgendem Schema aufgebaut: [Zustand],[Zeichen] [Neuer Zustand],[Neues Zeichen],[Richung]
Ein Programm mit der Zeile 1,x 2,y,> würde also beim Lesen eines x in den Zustand 2 übergehen, das x durch ein y ersetzen und den Kopf nach rechts bewegen.
Beispiel
Ein Programm, das zählt, wie oft der Buchstabe I auf dem Band vorhanden ist und das Ergebnis als Binärzahl ausgibt:
1,= 1,=,> 1,1 1,1,> 1,0 1,0,> 1,I 2,=,< 2,= 2,=,< 2,_ 1,1,> 2,0 1,1,> 2,1 2,0,<
Busy Beaver
Als "fleißige Bieber" werden endliche Turingprogramme bezeichnet, die versuchen mit möglichst wenigen Zuständen möglichst oft die Ziffer 1 auf das Band zu schreiben.
