Turingmaschine

Glossar
· Hauptseite · Zufälliger Artikel · Portal liste
Diskussion
· Diskussion : Turingmaschine
Webkatalog
· Übersicht · Eigene Artikel · Seite vorschlagen
Aktuelles
· Seite der Woche · Newsletter · Today in History · Kreuzworträtsel
Weitere Inhalte
· Einkaufsmeile · Begriffslexikon · Multimedia
Suche
· Geschi.de · nach Jahren · Weltchronik.de · Geschichtsreferate
Interna
· Seitenneuigkeiten · Hilfe zur Seite · Impressum

Jahres-Sprung
Jahreszahl eingeben: >Chronik2000-Homepage<

Turingmaschine

Stichpunkte

Allgemein
	um eine Klasse von berechenbaren Funktionen zu bilden
	Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes mathematisches Modell
	in der Schrift "On Computable Numbers
	Sie wurde im Rahmen des von David Hilbert im Jahr 1900 formulierten Hilbertprogramms
	"Verbergen") 1 Definition 1.1 Informelle Beschreibung 1.2 Formale Definition 2 Beispiel 3 Variationen des Turingmaschinen-Modells 4 Universelle Turingmaschine 5 Beziehung Turingmaschine - Formale Sprache 5.1 Akzeptierte Sprache 5.2 Entscheidbare Sprache 6 Allgemeines 7 Erweiterung 8 ErklÃ¤rung fÃ¼r Nicht-Mathematiker/Informatiker 9 Siehe auch 10 Literatur 11 Weblinks [Bearbeiten]
	speziell zur LÃ¶sung des so genannten Entscheidungsproblems
	with an Application to the Entscheidungsproblem" vorgestellt. Inhaltsverzeichnis showTocToggle("Anzeigen"
Definition
	[Bearbeiten]
Informelle Beschreibung
	1-Band Turingmaschine Die Turingmaschine besteht aus einem unendlich langen Speicherband mit unendlich vielen Feldern
	In jedem dieser Felder kann genau ein Zeichen gespeichert werden. einem Schaltwerk mit endlich vielen ZustÃ¤nden
	Es steuert das Verhalten der Turingmaschine. einem programmgesteuerten Lese- und Schreibkopf
	der auf dem endlosen Speicherband ein Feld nach links oder rechts rÃ¼cken
	ein Zeichen lesen
	schreiben oder lÃ¶schen und stehen lassen kann. Eine Turingmaschine modifiziert also eine Eingabe auf dem Band nach einem gegebenen Programm
	Ist die Berechnung beendet
	so befindet sich das Ergebnis auf dem Band
	Es wird somit jedem Eingabewert ein Ausgabewert zugeordnet
	Eine Turingmaschine muss aber nicht fÃ¼r alle Eingaben stoppen
	In diesem Fall ist die Funktion fÃ¼r die Eingabe undefiniert. Das Ergebnis der Berechnung wird manchmal als das definiert
	was nach dem Anhalten auf dem Band steht
	Wie die meisten Automaten wird die Turingmaschine jedoch meistens fÃ¼r Entscheidungsprobleme eingesetzt
	die mit "ja" oder "nein" zu beantworten sind
	also fÃ¼r Fragen
	Dabei wird das Anhalten der TM als "ja" interpretiert
	"nein" ist dem entsprechend durch das nicht-Anhalten signalisiert (Endlosschleife)
	indem man fragt
	Zu beachten ist dabei
	dass sich jedes Problem als Entscheidungsproblem formulieren lÃ¤sst
	ob ein bestimmter Wert eine LÃ¶sung fÃ¼r ein konkretes Problem ist. [Bearbeiten]
Formale Definition
	R }<math> ist die ÃœberfÃ¼hrungsfunktion <math>F subseteq Q<math> ist die Menge der End- bzw. akzeptierenden ZustÃ¤nde Die Turingmaschine arbeitet wie folgt: In einem bestimmten (Start-)Zustand liest sie ein Zeichen vom Band
	Formal kann eine deterministische Turingmaschine als 7-Tupel <math>M=(Q
	Sigma
	delta
	square
	Gamma
	F)<math> dargestellt werden. <math>Q<math> ist die endliche Zustandsmenge <math>Sigma subset Gamma<math> ist das endliche Eingabealphabet <math>Gamma<math> ist das endliche Bandalphabet <math>square in Gamma setminus Sigma<math> steht fÃ¼r das leere Feld <math>q_0 in Q<math> ist der Anfangszustand <math>delta : Q times Gamma rightarrow Q times Gamma times { L
	q_0
	0
	bewegt den Schreib-/Lesekopf in die vorgegebene Richtung und Ã¤ndert ihren internen Zustand
	in dem sie sich gerade befindet
	schreibt sie ein Zeichen auf das Band
	In AbhÃ¤ngigkeit vom gelesenen Zeichen und dem Zustand
	Dieser Vorgang wird durch die ÃœberfÃ¼hrungsfunktion realisiert
	Damit hat die TM einen Takt ihres Arbeitszyklus' durchlaufen und steht fÃ¼r einen weiteren bereit
	ist die Berechnung beendet
	Erreicht die Turingmaschine einen End-Zustand
	also einen Zustand der Menge <math>F<math>
	R } right)<math>
	0
	Das Ergebnis befindet sich dann auf dem Band. Im nichtdeterministischen Fall Ã¤ndert sich die ÃœberfÃ¼hrungsfunktion zu <math>delta : Q times Gamma rightarrow mathcal{P} left( Q times Gamma times { L
	Hierbei steht <math>mathcal{P}<math> wie Ã¼blich fÃ¼r die Potenzmenge. [Bearbeiten]
Beispiel
	Die folgende deterministische 1-Band-Turingmaschine <math>M<math> erwartet eine Folge von Einsen als Eingabe auf dem Band
	Sie verdoppelt die Anzahl der Einsen wobei ein Leersymbol in der Mitte stehen bleibt
	Aus "111" wird beispielsweise die Zeichenfolge "1110111"
	Der Schreib-/Lesekopf befindet sich initial auf der ersten Eins
	s5
	Sigma
	0
	der Endzustand <math>s6<math>. <math>M = (Q
	0}<math> * <math>F = {s6}<math> alter geles. schr. neuer Kopf- alter geles. schr. neuer Kopf- Zust
	F)<math> * <math>Q = {s1
	s1
	Gamma
	s3
	s2
	delta
	Der Anfangszustand ist <math>s1<math>
	s4
	s6}<math> * <math>Sigma = {1}<math> * <math>Gamma = {1
	Symbol Symbol Zust. richtg. Zust
	wobei die aktuelle Kopfposition fett gedruckt ist: Schritt Zust
	Symbol Symbol Zust. richtg. ------------------------------------ ------------------------------------ s1 1 -> 0 s2 R s4 1 -> 1 s4 L s1 0 -> 0 s6 0 s4 0 -> 0 s5 L s2 1 -> 1 s2 R s5 1 -> 1 s5 L s2 0 -> 0 s3 R s5 0 -> 1 s1 R s3 0 -> 1 s4 L s3 1 -> 1 s3 R <math>M<math> durchlÃ¤uft zum Beispiel bei der Eingabe "11" folgende ZustÃ¤nde
	Band Schritt Zust
	Band ------------------- ------------------- 1 s1 11 9 s2 1001 2 s2 01 10 s3 1001 3 s2 010 11 s3 10010 4 s3 0100 12 s4 10011 5 s4 0101 13 s4 10011 6 s5 0101 14 s5 10011 7 s5 0101 15 s1 11011 8 s1 1101 16 s6 -halt- Die Berechnung beginnt im Anfangszustand <math>s1<math>
	der Schreib-/Lesekopf bewegt sich nach rechts und neuer Zustand wird <math>s2<math>
	Hier wird die erste Eins durch eine Null ersetzt
	bis eine Null gelesen wird
	Der Kopf wandert nun solange nach rechts
	bis sie erneut eine Null findet
	Danach gelangt die Turingmaschine in den Zustand <math>s3<math> und Ã¼berliest alle weiteren Einsen
	Diese wird dann durch eine Eins ersetzt
	Zustandswechsel auf <math>s5<math>
	Ã¼berliest wieder alle Einsen
	Im Zustand <math>s4<math> bewegt sich der Kopf zurÃ¼ck
	bis er auf eine Null trifft
	Der Kopf bewegt sich nun solange nach links
	bis die ursprÃ¼nglich in Zustand <math>s1<math> geschriebene Null gefunden wird
	Diese wird wieder durch eine Eins ersetzt
	der Kopf bewegt sich ein Feld nach rechts und die Turingmaschine gelangt wieder in den Zustand <math>s1<math>
	Hier beginnt ein neuer Rechenzyklus
	so gelangt die Turingmaschine <math>M<math> in den Endzustand <math>s6<math>
	Wird im Zustand <math>s1<math> eine Null gelesen
	woraufhin die Berechnung beendet wird. [Bearbeiten]
Variationen des Turingmaschinen-Modells
	die sich jeweils in einigen Details unterscheiden
	In der Literatur findet man zahlreiche unterschiedliche Definitionen der Turingmaschine
	So variieren etwa die Anzahl der BÃ¤nder
	das verwendete Bandalphabet
	die zusÃ¤tzlich verwendeten Spezialzeichen und andere Eigenschaften
	Die Vielfalt ist theoretisch durch die These von Church gerechtfertigt
	welche im Hinblick auf die Berechenbarkeit die Ã„quivalenz aller universellen Maschinenmodelle postuliert
	Selbst komplexitÃ¤tstheoretisch sind die Unterschiede zwischen verschiedenen Definitionen weitgehend zu vernachlÃ¤ssigen
	So lÃ¤sst sich etwa jede f(n)-zeitbeschrÃ¤nkte k-Bandmaschine mit beliebig groÃŸem k durch eine nur O(fÂ²(n))-zeitbeschrÃ¤nkte 1-Bandmaschine simulieren
	Der Mehraufwand fÃ¼r die Simulation beliebig vieler BÃ¤nder kommt es also zu einem maximal quadratischen Mehraufwand
	Insgesamt fÃ¼hren alle Arten von Variationen zu nicht mehr als polynomialen Aufwandsunterschieden (wobei Aufwand hier eine beliebige Ressource meint) und sind daher fÃ¼r viele komplexitÃ¤tstheoretische Untersuchungen vernachlÃ¤ssigbar
	dass die Analyse mÃ¶glichst einfach durchgefÃ¼hrt werden kann. [Bearbeiten]
	Man passt in AbhÃ¤ngigkeit von den Zielen der jeweiligen Analyse das verwendete Modell so an
Universelle Turingmaschine
	In der obigen Definition ist das Programm fest in die Maschine eingebaut und kann nicht verÃ¤ndert werden
	die die Kodierung einer Turingmaschine als Teil ihrer Eingabe nimmt
	Man kann aber eine universelle Turingmaschine definieren
	und das Verhalten der kodierten Turingmaschine auf der ebenfalls gegebenen Eingabe simuliert. (Das analoge Konzept bei Programmiersprachen ist der Interpreter)
	liegt auch fast allen heutigen Rechnerarchitekturen zugrunde (Von-Neumann-Architektur). [Bearbeiten]
	bei der das Programm als ein Teil der verÃ¤nderbaren Eingabedaten betrachtet wird
	Aus der Existenz einer solchen universellen Turingmaschine folgt z. B. die Unentscheidbarkeit des Halteproblems. Eine Ã¤hnliche Idee
Beziehung Turingmaschine - Formale Sprache
	[Bearbeiten]
Akzeptierte Sprache
	wenn sie bei Eingabe eines jeden Wortes x âˆˆ L nach endlich vielen Schritten in einen der definierten EndzustÃ¤nde Ã¼bergeht
	Eine Turingmaschine akzeptiert eine Sprache L
	HÃ¤lt die Turingmaschine in einem anderen Zustand oder geht sie in eine Endlosschleife
	dann wird die Eingabe x von ihr nicht akzeptiert
	die L akzeptiert. [Bearbeiten]
	Eine Sprache <math>L subseteq Sigma^{star}<math> heiÃŸt genau dann rekursiv aufzÃ¤hlbar
	wenn es eine deterministische Turingmaschine gibt
Entscheidbare Sprache
	die nicht zu dieser Sprache gehÃ¶ren
	Akzeptiert eine Turingmaschine eine Sprache und hÃ¤lt sie zusÃ¤tzlich bei allen Eingaben
	so entscheidet die Turingmaschine diese Sprache
	Eine Sprache <math>L subseteq Sigma^{star}<math> heiÃŸt genau dann rekursiv bzw. entscheidbar
	wenn es eine deterministische Turingmaschine gibt
	die L entscheidet. [Bearbeiten]
Allgemeines
	z. B. Ã¼ber rekursive Funktionen
	die sich mit einer Turingmaschine berechnen lassen (die Turingmaschine muss die Aktion (H) ausfÃ¼hren!). Es gibt noch andere Verfahren
	Die Menge der Turing-berechenbaren Funktionen ist die Menge aller Funktionen
	Ã¼ber die man Berechenbarkeit von Funktionen definieren kann
	liegt die Vermutung nahe
	Da andere Verfahren aber nachweislich dieselbe Klasse von Funktionen beschreiben wie die der Turingmaschine
	dass alle (intuitiv) berechenbaren Funktionen bereits durch das einfache Modell der Turingmaschine berechnet werden kÃ¶nnen
	Dieses Ergebnis der Berechnungstheorie wird in der Churchschen These zusammengefasst. Es macht Ã¼brigens keinen Unterschied
	ob eine Turingmaschine ein oder mehrere BÃ¤nder verwendet
	Auch das Bandalphabet kann beliebig groÃŸ sein; solange neben dem Leerzeichen ein weiteres Zeichen enthalten ist
	ist eine Turingmaschine zur allgemeinen Turingmaschine gleich mÃ¤chtig
	AuÃŸerdem ist beweisbar
	dass sich mehrbandige Turingmaschinen durch eine einbandige simulieren lassen
	Ein beliebtes Problem ist der FleiÃŸige Biber: Man finde die Turingmaschine
	die mit einer bestimmten Anzahl von ZustÃ¤nden die maximale Anzahl von "1"-Symbolen auf das Band schreibt und dann anhÃ¤lt
	mit sehr einfachen Regeln und sehr verblÃ¼ffenden Ergebnissen
	Chris Langtons Ameise ist eine Turingmaschine mit zweidimensionalem Band
	Eine Abbildung und einen erklÃ¤renden Text findet man unter Ameise (Turingmaschine). [Bearbeiten]
Erweiterung
	das von der Turingmaschine nicht gelÃ¶st werden kann
	die besagt
	Eine Erweiterung bildet die Church-Turing-These
	dass ein Problem
	auch von keinem Menschen gelÃ¶st werden kÃ¶nnte. [Bearbeiten]
ErklÃ¤rung fÃ¼r Nicht-Mathematiker/Informatiker
	Das faszinierende an einer Turing-Maschine ist
	dass sie mit nur drei Operationen (lesen
	schreiben und Kopf bewegen) alle lÃ¶sbaren Probleme lÃ¶sen kann
	SÃ¤mtliche mathematischen Grundfunktionen
	wie Addition und Multiplikation lassen sich mit diesen drei Operatoren simulieren
	usw
	Aufbauend darauf lassen sich wiederum sÃ¤mtliche restlichen vorhandenen mathematischen Funktionen erzeugen
	Dieses Konzept heisst Church-Turing-These: Eine Turingmaschine kann alle intuitiv lÃ¶sbaren Probleme lÃ¶sen
	und somit unlÃ¶sbar ist
	so wird unsere Turingmaschine die Frage ob sie anhÃ¤lt nie mit "nein" beantworten kÃ¶nnen. (siehe Halteproblem) Ein Computer kann als eine Implementierung der Turing-Maschine angesehen werden â€“ er operiert nur mit Nullen und Einsen (aber hier nicht unendlich vielen)
	denn angenommen die andere Turingmaschine lÃ¤uft unendlich lange (terminiert nicht)
	ist folgendes: â€žFinde eine Turingmaschine
	und schafft es
	Ein Problem
	damit die komplexesten Dinge zu berechnen. [Bearbeiten]
	ob eine andere Turingmaschine bei einer gewissen Eingabe jemals anhÃ¤lt.â€œ So eine Turingmaschine kann es nicht geben
	die bestimmt
	das eine Turingmaschine nicht beantworten kann
Siehe auch
	Von-Neumann-Maschine Goto-Programm linear beschrÃ¤nkte Turingmaschine (LBA) Nichtdeterministische Turingmaschine (NTM) LOOP-Programm WHILE-Programm Automatentheorie [Bearbeiten]
Literatur
	A.
	Wien / New York: Springer-Verlag 1998
	ISBN 3-211-82769-2 Turing
	Volume 42
	Oswald Wiener
	With an Application to the Entscheidungsproblem (http://www.abelard.org/turpap2/tp2-ie.asp)
	Manuel Bonik
	Robert HÃ¶dicke: Eine elementare EinfÃ¼hrung in die Theorie der Turing-Maschinen
	On Computable Numbers
	1936; reprinted in M
	Proceedings of the London Mathematical Society
	Series 2
	Hewlett
	NY: Raven Press
	David (ed.)
	Symbolische Maschinen
	1965 Sybille KrÃ¤mer
	The Undecidable
	Englewood Cliffs
	ISBN 3-211-82637-8 Heinz LÃ¼neburg: Rekursive Funktionen
	ISBN 3-540-43094-6 Marvin Minsky: Computation: Finite and Infinite Machines
	N.J.: Prentice-Hall 1967 B.A
	Wien / New York: Springer Verlag
	Darmstadt: Wissenschaftliche Buchgesellschaft 1988 Rolf Herken: The Universal Turing Machine - A Half-Century Survey
	Die Idee der Formalisierung im geschichtlichen AbriÃŸ
	Springer-Verlag
	Berlin: VEB Deutscher Verlag der Wissenschaften 1977 [Bearbeiten]
	Trachtenbrot: Algorithmen und Rechenautomaten
Weblinks
	Die Turing-Maschine (http://www.turing-maschine.de) - Ãœber berechenbare Zahlen mit einer Anwendung auf das Entscheidungsproblem Turing-Maschine Simulator (http://wwwsys.informatik.fh-wiesbaden.de/weber1/turing/tm.html) Theoretische Informatik (http://oberstufeninformatik.de/theorie/) bg:ÐœÐ°ÑˆÐ¸Ð½Ð° Ð½Ð° Ð¢ÑŽÑ€Ð¸Ð½Ð³ cs:TuringÅ¯v stroj en:Turing machine es:MÃ¡quina de Turing fi:Turingin kone fr:Machine de Turing he:×ž×›×•× ×ª ×˜×™×•×¨×™× ×’ hu:Turing-gÃ©p it:Macchina di Turing ja:ãƒ?ãƒ¥ãƒ¼ãƒªãƒ³ã‚°ãƒžã‚·ãƒ³ ko:íŠœë§? ê¸°ê³„ lt:Tiuringo maÅ¡ina nl:Turingmachine pl:Maszyna Turinga pt:MÃ¡quina de Turing ru:Ð£Ð½Ð¸Ð²ÐµÑ€Ñ?Ð°Ð»ÑŒÐ½Ð°Ñ? Ð¼Ð°ÑˆÐ¸Ð½Ð° Ð¢ÑŒÑŽÑ€Ð¸Ð½Ð³Ð° sl:Turingov stroj sv:Turingmaskin tr:Turing Makinesi zh:å›¾ç?µæœº

[X] Schliessen

Dieser Artikel basiert auf dem Artikel Turingmaschine aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.