Diskussion:Turingmaschine

Frage zu Ausdruck

Weiss jemand, woher der Ausdruck Turing-Maschine stammt? Hat A. Turing des Ausdruck selbst gebraucht, wenn ja wo? (das müsste doch im Artikel stehen, oder?) Rolf Todesco 19:18, 3. Dez. 2006 (CET)

Brainfuck

Brainfuck ist zwar kein netter Name, aber aktuell ist es eine sehr gute möglichkeit selbst einmal eine Turingmaschine auszuprobieren bzw. zu programmieren. Ich denke das muss unbedingt in den artikel aufgenommen werden, bzw. verlinkt werden.

Es gibt zig solcher Tools, sicher auch mit etwas weniger anstössigen Namen. Du solltest dein Anliegen daher schon Begründen. --matrixx 16:32, 17. Mär 2006 (CET)

Erklärung für Nicht-Informatiker

Warum wurde das rausgeschmissen ? Ich finde es wichtig, das auch nicht-studierte wissen was für ein wichtiges Konzept das ist, desshalb hatte ich das vor Urzeiten mal reingenommen. Wie ich sehe wurde es dann von 62.134.230.134 total verwässert und später komplett rausgenommen. --matrixx 14.10.05

ALso ich habe zwar mit diesem Absatz nichts zu tun, aber ich finde das der ganze Artikel und vorallem die Einleitung auch für Nicht-Informatiker verständlich sein sollte - wie es eben in einer Enzyklopädie üblich ist. So ein Abschnitt sollte also unnötig sein, wenn der Artikel gut geschrieben ist. Inwieweit das der Fall ist wage ich mal nicht zu beurteilen, da ich wahrscheinlich zu "vorbelastet" bin. Ich verstehe ihn jedenfalls ganz gut. --87.123.34.199 18:53, 14. Okt 2005 (CEST)

Im Moment gibt es eine Einleitung, die ich unbefriedigend finde, die man aber nicht bearbeiten kann.

Also ich bin Nichtmathematiker und -informatiker und ich versteh ehrlich gesagt nur Bahnhof.

Das ist selbst für angehende Informatiker ziemlich unverständlich. Dieses ganze Formelgesülze gehört eigenlich nicht in ne Enzyklopädie, es fehlt einfach eine Definition, die selbst für absolute nicht-Informatiker ist. --Lennartb 21.11.07

Hallo Lennartb, du hast den Unverständlich-Baustein gesetzt. Ich habe den Abschnitt "Informelle Beschreibung" eben noch etwas überarbeitet/ausgebaut und halte die Einleitung und diesen Abschnitt auch für Nicht-Informatiker verständlich. Nenne bitte konkrete Stellen oder stell konkrete Fragen, ansonsten werde ich den Baustein demnächst wieder entfernen. -- Klara 15:47, 22. Nov. 2007 (CET)

Hallo Klara, die Einleitung halte ich jetzt ebenfalls für verständlich - danke dafür. Allerdings finde ich beispielsweise den Abschnitt "Formale Definition" bereits schon wieder verwirrend. Allein um die Einleitung zu verstehen, braucht man Mathematik-Kenntnisse die über das Klasse 13/Abitur-Mathe hinausgehen, bzw. muss sich erstmal die Definitionen von "deterministische" und "7-Tupel" zu Gemühte führen. Wenn ich mir für das Verständnis eines Enzyklopädie-Artikels, erst 5 andere Artikel durchlesen muss, finde ich das etwas...unglücklich.--Lennartb 20:40, 22. Nov. 2007 (CET)

Ich stimme dir zu, dass es schwierig ist, die formale Definition ohne Vorwissen/Übung zu verstehen. Es gibt nun aber Dinge, die können gar nicht ohne Vorwissen oder zumindest Vorarbeit (darunter fällt auch das Lesen von verlinkten Artikeln) verstanden werden. Denn man kann nicht in jedem Artikel bei Adam und Eva anfangen. Das wird besonders in abstrakten Bereichen (ganz extrem in der Mathematik) deutlich. Natürlich kann man damit auch nicht jede Kritik an der Verständlichkeit erschlagen, natürlich muss die Verständlichkeit erstmal das Ziel sein, darf aber auch nicht dazu führen, dass man ungenau wird (schon gar nicht im formalen Teil, dafür ist dann der informelle da). Bei komplizierteren Themen muss man aber vor allem darauf achten, dass es inhaltlich korrekt und verwendete Begriffe verlinkt sind. Wir haben in der Wikipedia die Möglichkeit, längere Artikel zu schreiben als in einer Enzyklopädie in Papierform, das muss ja nicht ungenutzt bleiben. Zu deiner konkreten Anmerkung: Die Funktionsweise, die hier beschrieben wird (im informellen sowie im formalen Teil) ist die der deterministischen Turingmaschine. Deterministisch heißt, dass es eine Funktion gibt, die für jeden Schritt eindeutig festlegt, was passiert. Das ist bei der nichtdeterministischen anders, es gibt verschiedene Möglichkeiten (daher ist es dort auch keine Funktion mehr, denn eine Funktion ordnet einem Element der Definitionsmenge immer eindeutig ein Element der Zielmenge zu). Das könnte man tatsächlich noch mehr ausformulieren und schon vorher sagen, dass es um hier um die deterministische Turingmaschine geht. Den Unverständlich-Baustein entferne ich dann jedenfalls mal. Viele Grüße -- Klara 23:45, 22. Nov. 2007 (CET)

Der Fehler im Artikel Turingmaschine muss raus!

---

Hier möchte ich darauf hinweisen, dass es einen schwerwiegenden Fehler in diesem Artikel gibt!

Implizit wird erklärt, dass eine TM nur dann nicht terminiert, wenn sie in eine Endlosschleife gerät. Das ist schlichtweg falsch.

Meine Verbesserung wurde von Squizzz rückgängig gemacht. Er hat meinen Kommentar noch nicht beantwortet.

Sicher sind alle der Ansicht, dass wir auf alle Fälle Wahrheiten verbreiten sollten. Ich bitte um Vorschläge, wie das zu erreichen ist.

Viele Grüße

--Gerhard Buntrock 03:22, 12. Sep 2005 (CEST)

---

in beide Richtungen unsichtbares Band

Müsste es nicht heissen:

in mindestens eine Richtung unendliches Band

Normalerweise startet eine Turingmaschine an der linken festen Seite eines unendlich langen Bandes, ja. --avatar

'Normalerweise' 'links' - nie im Leben! Es gibt viele Konventionen fuer Turing-Maschinen, und eine ist eben das (nur) einseitig unendliche Band. Aber das ist deswegen nicht in irgendeine bestimmte Richtung (nur) einseitig unendlich. Und was meinst Du mit der 'festen Seite'? Die Seite, nach der hin das Band nicht unendlich ist? Eine TM startet auf dem Feld (und in dem Zustand), das (den) ihr die Umgebung zuweist. Die Umgebung kann z.B. eine uebergeordnete TM sein. Bei einer TM mit einem nach beiden Seiten unendlichen Band kann das Startfeld z.B. dasjenige sein mit dem ersten nichtleeren Feld, und das koennte das erste von links sein, aber eben auch von rechts, je nach gewaehlter Konvention. (Uebrigens soll Turing ziemlich Links-Rechts-Schwaechen gehabt haben. Hat manchmal ganze Vortraege in Spiegelschrift an die Tafel gechrieben, bis ihn jemand darauf hinwies.) Ist das Band nur in eine Richtung unendlich, kann man als Konvention festlegen, dass - falls es nach rechts unendlich ist - das Startfeld das erste nichtleere Feld einer Zeichenkette ist, und zwar links, und das dieses stets mit dem ersten (von links aus gesehen) Feld des Bandes ueberhaupt zusammenfaellt. Das komplexere Problem in diesem Zusammenhang ist die Verwendung von 'unendlich'. Meint man 'aktual unendlich' oder 'potentiell unendlich'? - Natuerlich letzteres. Aber richtig richtig ist 'beliebig lang' - immer, wenn es der Rechenprozess erfordert, stiftet die Umgebung ein weiteres Feld. -- Manuel Bonik

---

Es macht übrigens keinen Unterschied, ob eine Turing-Maschine eine oder mehrere Bänder verwendet. Ist das sicher? Ich habe gehört, es gebe Funktionen, die könnten mit zwei Bändern, aber nicht mit einem berechnet werden... -- Fgb

Aus dem hohlen Bauch heraus sage ich jetzt mal, dass es solche Funktionen nicht geben kann. Die Bänder sind abzählbar unendlich, d.h. es gibt eine Bijektion zwischen ihnen, und die muss die Turing-Maschine ausführen können. D.h. also, die T.M. kann mit einem Band zwei Bänder "emulieren". Der Rechenaufwand mag dabei steigen, aber letztendlich bleibt er von gleicher Ordnung, lediglich die Konstante ändert sich. -- Flups

Es gibt beliebige Speicher (im allgemeinen ein beliebiger Graph), also nicht nur Bänder. Die können alle die gleichen Funktionen berechnen, aber mit unterschiedlicher Effizienz. --Vulture

Turingmaschinen mit mehreren Bändern haben definitiv nicht mehr Rechenpower als Turingmaschinen mit einem Band!

---

Wie schreibt man denn Turingmaschine jetzt? Turing-Maschine oder Turingmaschine? Google spuckt ca. 12200 Ergebnisse für "Turing-Maschine" und ca. 12300 für "Turingmaschine" aus, ist also auch nicht sehr aussagekräftig ... :)

Ich hab auf jeden Fall die Schreibweise im Artikel dem Titel angepasst ... --brunft 10:54, 12. Mär 2004 (CET)

-- Nach den neuen Regeln der Rechtschreibreform sind beide Schreibweisen möglich. Siehe http://www.ids-mannheim.de/reform/c3.html

§ 51: Man kann einen Bindestrich in Zusammensetzungen setzen, die als ersten Bestandteil einen Eigennamen haben, der besonders hervorgehoben werden soll, oder wenn der zweite Bestandteil bereits eine Zusammensetzung ist.

Hutschi

---

Eine Maschine mit zwei nichtgetakteten Bändern, könnte die mächtiger sein, als eine Turingmaschine? Hier spielte ja dann der Zufall eine Rolle. (Ich nenne sie nicht "Turingmaschine", denn es ist ja keine.)

Wenn eine Fliege da wäre, die sich auf das Band setzt und dafür sorgt, dass ein Zeichen nicht erkennbar wird, wäre die Maschine mächtiger, als die entsprechende Turingmaschine?

(Es wäre eine Turingmaschine, die irren kann.)

-- Hutschi 13:42, 16. Mär 2004 (CET)

Wenn man Zufallsfaktoren ins Spiel bringt, werden die Ergebnisse sicherlich mannigfaltiger. Aber das entspraeche nicht der Definition von TMn als deterministischen Maschinen. Turing sieht immerhin auch eine Zufallsmaschine vor, mit dem schoenen Namen 'Orakel'. Nicht-deterministische TMn sind als solche definiert, die jeweils die Wahl zwischen mehreren Folge-Zustaenden haben. Aber die koennen auch nicht mehr als determistische TMn. Vgl. unten. - Manuel Bonik

---

"Turing zeigte, dass diese Maschine jedes algorithmisierbare (berechenbare) Problem lösen kann."

Das verstehe ich so, dass Turing die Churchsche These zumindest in eine Richtung bewiesen hat. Laut dem entsprechenden Artikel ist diese These aber unbeweisbar. Missverstehe ich den Artikel, ist die andere Richtung schwieriger oder liegt hier ein Fehler vor?

-- Boogieman

Der Satz ist meiner Meinung nach zwar nicht falsch, aber sinnlos - wenn mit "berechenbar" Turing-berechenbar gemeint ist. Turing gab ja mit diesem Modell erst eine Definition von "Berechenbarkeit" an, die mit anderen Modellen nachweislich dieselbe Klasse von Funktionen beschreibt. Die Churche These ist und bleibt unbeweisbar. Ich habe den Satz erst einmal entfernt. --zap 14:30, 28. Jun 2004 (CEST)

---

Ganz allgemein bin ich mit dieser Seite der Wikipedia unzufrieden. Die Seite erklärt zwar, was eine Turingmaschine ist, erhellt dieses aber nur für Mathematiker. Es fehlt eine allgemein verständliche Erklärung und Einführung. So wie die Seite hier steht, ist sie nur für Mathematiker und Informatiker von Interesse, aber für diese Zielgruppe ist die Wikipedia eigentlich nicht da.

--Henrik Fisch 13:56, 19. Apr 2004 (CEST)

Außerdem wird nicht erklärt, was es mit dem ominösen Nichtdeterministisch auf sich hat. -- Nichtich

Nichtdeterministisch im Gegensatz zu deterministisch bedeutet im Falle der Turingmaschine, das das Programm der Turingmaschine in einer besonderen Konfiguration (gemeint ist; mit einem bestimmten gelesenen Zeichen und einem bestimmten Zustand - also die Linke Seite der Programmvorschrift) mehrere Folgekonfigurationen enthält, von denen nur eine ausgewählt wird. Die deterministische TM kennt nur einen Folgezustand.

lies doch mal Nichtdeterminismus ;-) Pinguin.tk 14:14, 7. Jul 2004 (CEST)

---

Die Turingmaschine [..] wurde zur Lösung des von Kurt Gödel formulierten Vollständigkeitsproblems erdacht.

Gödel bewies seinen Unvollständigkeitssatz 1930. Turing hat seine Arbeit aber erst 1937 veröffentlicht ("On computable numbers, with an application to the Entscheidungsproblem"). Weiß jemand mehr über den Zusammenhang von Unvollständigkeitssatz und Turingmaschine? --zap 13:03, 16. Jul 2004 (CEST)

Die TM wurde zur Lösung des Entscheidungsproblems erdacht, wie der Titel von Turings Aufsatz ja schon sagt. Wer das Entscheidungsproblem genau gemacht hat, weiss ich nicht. Aber Turing reagierte auf das sogenannte Hilbertsche Programm vom Mathematikerkongress 1900 in Paris. -- Manuel Bonik

Ich sehe gerade das es ja um den Vollständigkeitssatz geht (nicht Unvollständigkeit), was die Sache aber nicht besser macht - Gödel hat auch den Vollständigkeitssatz lange vor Turing's Publikation bewiesen (nämlich 1929 - siehe engl. Wikipedia en:Gödel's_completeness_theorem). Ich schätze der o.g. Satz ist einfach falsch. --zap 12:53, 31. Aug 2004 (CEST)

fleißiger Biber

Die Aussage, dass man fleißiger Biber nicht mit Zahlen über 4 berechnen kann, ist falsch, in dem Artikel über fleißiger Biber sind z.b. höhere Zahlen angeführt, es wurde aber zumindest bis 12 berechnet.

Der Satz lautete: Für 1 bis 4 Zustände konnte das Problem berechnet werden, aber bereits für "nur" 5 Zustände ist der "beste" Fleißige Biber noch nicht bekannt. Das ist nach meinem Wissen korrekt. Der derzeit fleißigste Biber mit 5 Zuständen produziert 4098 Einsen. Ob es aber der beste ist, ist nicht bekannt.--zap 14:45, 14. Dez 2004 (CET)

"Halteproblem"

In der obigen Definition ist das Programm fest in die Maschine eingebaut und kann nicht verändert werden. Man kann aber eine universelle Turingmaschine definieren, welche die Kodierung einer Turingmaschine als Teil ihrer Eingabe nimmt, und das Verhalten der kodierten Turingmaschine auf der ebenfalls gegebenen Eingabe simuliert. Aus der Existenz einer solchen universellen Turingmaschine folgt z. B. die Unentscheidbarkeit des Halteproblems. Eine ähnliche Idee, bei der das Programm als ein Teil der veränderbaren Eingabedaten betrachtet wird, liegt auch fast allen heutigen Rechnerarchitekturen zugrunde (Von-Neumann-Architektur). Eigentlich reicht bereits die normale Turing-Maschine und die Möglichkeit der Gödelisierung von Turing-Programmen aus, um das Halteproblem zu beweisen.

Fragen

Was heißt schreiben ?

Eine der 3 grundlegenden Funktionen der Turingmaschine ist das Schreiben. Wird dabei der vorhandene Eintrag auf dem Band überschrieben ? Oder wird eingefügt ? Links oder rechts eingefügt ?

Schreiben heisst überschreiben: das zuletzt gelesene Zeichen wird immer ersetzt (möglicherweise wieder durch das selbe Zeichen). -- D. Dÿsentrieb ⇌ 16:13, 13. Aug 2005 (CEST)

Gibt es gute didaktische Beispiele einer Turingmaschine in verschiedenen Programmiersprachen ?

Turingmaschinen eignen sich kaum für "reale" Programme, Implementationen von Turingmaschinen in höheren Programmiersprachen sind selten elegant. Es gibt aber reichlich visuelle Turingmaschinen-Simulatoren, google einfach mal: [1] oder [2]. Ich fand das hier ganz anschaulich [3], aber das Ding kann nur ein Programm. Flexibler aber nicht so hübsch ist diese Variante [4].

Hier ist noch eine TM, implementiert in Java [5] - hab' ich aber nicht ausprobiert. HTH -- D. Dÿsentrieb ⇌ 16:13, 13. Aug 2005 (CEST)

Endlosschleife

Es wurde die Behauptung aufgestellt, dass eine Turingmaschine auch nie halten kann ohne in eine Endlosschleife zu gehen. Das ist meines Erachtens falsch. Das die Zustandsmenge und das Bandalphabet endlich sind, sind auch die Definitionsmenge $Q\times \Gamma$ und die Bildmenge $Q\times \Gamma \times \{L,0,R\}$ der Übergangsfunktion endlich. Damit muss die Turingmaschine, wenn sie nicht hält, irgendwann wieder auf ein Tupel aus $Q\times \Gamma$ stoßen bei dem sie schon einmal war und gerät dann in eine Endlosschleife. --Squizzz 15:32, 9. Sep 2005 (CEST)

Du vergisst den Bandinhalt. Weiterhin müssen wir uns über den Begriff der Schleife einigen. Eine Schleife ist sicher dann gegeben, wenn alles, Bandinhalt, Position und Zustand sich wiederholen. Abstraktere Schleifen entstehen, wenn die Maschine z.B. immer eine 1 schreibt und nach rechts geht. Noch abstrakter wird es, wenn sie einmal ganz nach rechts geht, eine 1 schreibt und dann ganz nach links geht und eine 1 schreibt und jetzt wieder nach rechts, ...; offenbar ist jetzt der Schleifendurchgang nicht mal mehr immer gleich lang! Es wird offensichtlich, dass die Maschinen noch viel kompliziertere Schleifen durchlaufen können. Irgendwann kann ich das nicht mehr als Schleife akzeptieren. Denn genau die, die wir nicht mehr verstehen, machen das Halteproblem unentscheidbar. Hier sind Rechenwege drin, die wir rekursiv nicht entscheiden können, prinzipiell nicht! Wenn alles Schleifen wären, könnten wir das Halteproblem entscheiden! Denn jede Schleife, egal wie wir sie definieren --- ich denke, hier sind wir uns bestimmt einig --- ist eine entscheidbare Eigenschaft. Daher dürfen wir nicht sagen, dass der einzige Grund des Nichthaltens eine Endlosschleife sein kann. Das ist definitiv falsch. Daher konnte ich mich nicht beherrschen und habe meinen Beitrag eingefügt. ;-)

Viele Grüße --Gerhard Buntrock 16:51, 9. Sep 2005 (CEST)

Ab dem Satz „Denn genau die, die wir nicht mehr verstehen, machen das Halteproblem unentscheidbar.“ kann ich dir nicht mehr folgen. Insbesondere ist mir unklar, warum die Terminierung einer Schleife entscheidbar ist: das Halteproblem selbst benutzt eine While-Schleife. Nichtsdestotrotz habe ich den letzten Hinweis auf die Endlosschleife gelöscht, der noch übrig war. Noch eine Bitte: schreibe doch hier in er Diskussion linear und ohne Einrückungen und übermäßigen Gebrauch von Trennlinien. --Squizzz 08:15, 12. Sep 2005 (CEST)

Luecke in der Schlussfolgerung

Im Aritkel steht: So kann etwa an Hand des Halteproblems gezeigt werden, dass es mathematische Funktionen gibt, die nicht von Menschen (und folglich auch nicht von einer Turingmaschine) berechnet werden können.)

Dort wird also behauptet, dass eine Turingmaschine etwas nicht berechnen kann, was auch ein Mensch nicht berechnen kann. Aber wo wird bewiesen, dass eine Turingmaschine auf das beschraenkt ist, was ein Mensch kann? Bisher ist doch erst die eine Richtung bewiesen, dass sie mindestens die Maechtigkeit eines Menschen hat.

-- Gruss sparti 13:59, 12. Nov 2005 (CET)

Behauptet das aber nicht gerade die (nicht bewiesene, jedoch allgemein als korrekt angenommene) Church-Turing-These? Stern !? 14:05, 12. Nov 2005 (CET)

Doch das stimmt. Man koennte es hier aber nochmal erwaehnen. Trotzdem Danke. -- sparti 19:17, 12. Nov 2005 (CET)

Es wurde nirgendwo bewiesen, dass eine Turingmaschine mindestens so mächtig wie ein Mensch ist. Denn das ist genauso unbeweisbar wie die Churche These!

Kleine Änderungen an der Formalen Definition

In disem Artikel stand in der Formalen Definiton das: $\Sigma \subset \Gamma$ das endliche Eingabealphabet sei, dieses halte ich für falsch, geanuso wie: $\square \in \Gamma \setminus \Sigma$ steht für das leere Feld. Ich meine dieses ist falsch, da die Turingmaschien auch das leere Feld schreiben können muss, sonst würde es nicht möglich sein, wenn ein Zeichen in einem Feld steht, dieses durch das leere Feld zu ersetzen, da die Turingmaschine dieses nicht schreiben könnte. Daher meine ich, muss die erste Definition $\Sigma \subseteq \Gamma$ das endliche Eingabealphabet heißen (allso das leere Feld mit einbeziehen). Daraus folgt dann, dass die zweite Definiton nicht möglich ist, da $\Gamma$ dann gleich $\Sigma$ ist und das leere Feld dann nicht mehr definiert wäre.

Aus diesm Grund, musste dann auch das Beispiel geändert werden und zwar muss in die Menge $\Sigma$ auch noch das leere Feld aufgenommen werden, dieses ist auch logisch, denn wenn die Maschine kein leeres Feld schreiben könnte, könnte es aus einer 1 auf dem Band kein leeres Feld machen, dass dieses aber nötig ist, sieht man an dem Beispiel.

Daher habe ich diese beiden Punkte in dem Artikel verändert. Falls einer begründet anderer Meinung ist kann er es ja wieder ändern.

MfG
Ulf Buse (geschrieben: 1.12.2005)

Hallo Ulf, ich bin tatsächlich anderer Meinung: In allen Definition von Turingmaschinen, die ich kenne, ist $\square \not \in \Sigma$. Das hat auch einen guten Grund: $\Sigma$ ist das Eingabealphabet, und $\square$ ist kein Zeichen der Eingabe. Das würde auch zu Verwicklungen führen, da das Eingabewort ja zu Beginn auf dem Eingabeband steht, das sonst mit $\square$ gefüllt ist. Wenn jetzt $\square$ Teil des Eingabealphabets ist, dann ist ja gar nicht klar, was jetzt das Eingabewort ist, etwa "Wort" oder "$\square \dots \square$Wort$\square \dots \square$"...? Natürlich soll die Turingmaschine Zeichen löschen können, dafür muss aber $\square$ nicht Teil des Eingabe- sondern nur des Bandalphabets sein. Das ist ja aber durch $\square \in \Gamma \setminus \Sigma$ gesagt.

Also, ich habe den Artikel dementsprechend (zurück) geändert.

Gruß --eo !? 23:10, 1. Dez 2005 (CET)

Laut Introduction to the Theorie of Computation von Michael Seipser ist das Blank-Symbol definitiv nicht im Eingabesymbolvorrat enthalten. Das sollte soweit korrekt sein, da dieses Symbol eben ein Zeichen ist, welches nur auf dem Band erlaubt ist und eben als Markierung für freie Zellen gedacht ist. Jedoch ist das Blank-Symbol laut Seipser nicht bestandteil des 7-Tupels der Turing-Maschine sondern statt dessen die Reject-Zustände. Dieses sollte m.E. statt dessen eher angepasst werden. Die Definition lautet wie folgt:

A Turing machine is a 7-tuple, $(Q,\Sigma ,\Gamma ,\delta ,q_{0},q_{a}ccept,q_{r}eject)$, where $Q,\Sigma ,\Gamma$ are all final sets and

• $Q$ is a set of states,
• $\Sigma$ is the input alphabet not containing the blank symbol $\square$
• $\Gamma$ is the tape alphabet, where $\square \in \Gamma$ and $\Gamma \supset \Sigma$,
• $\delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}$ is the transition function,
• $q_{0}\in Q$ is the start state
• $q_{a}ccept\ inQ$ is the accept state, and
• $q_{r}eject\in Q$ is the reject state, where $q_{a}ccept\not =q_{r}eject$

Wie gesagt. Das Blank gehört nicht in das Eingabealphabet, da es ein Bandsymbol ist und eben nur eine leere Stelle auf dem Band markiert. Dennoch scheint es auch andere Definitionen einer Turing-Maschine zu geben. Es ist die Frage, welche nun die richtigere ist. Auf jeden Fall ermöglicht die vorhandene Definition nicht das explizite Zurückweisen einer Eingabe. Dies ist zwar bei Kellerautomaten und nichtdeterministischen endlichen Automaten auch der Fall, kenne ich aber eben bei Turing-Maschinen anders.

MfG FG

Unendlichkeit und das Halteproblem

Geht es nicht schon damit los, daß ein Teil der Turing-Maschine ein unendliches (sic!) Speicherband sei? Gibt es eine mathematische Unschärferelation? Gödel hat ja nur "nein" gesagt.

Eine Turing-Maschine hat soviel Speicherband, wie sie jeweils gerade braucht. Sie kriegt sozusagen auf Anfrage eine weiteres Feld. Das Speicherband ist potentiell, aber nicht aktual unendlich.

Tatsächlich ist es völlig egal, ob das Speicherband aktual oder potentiell unendlich ist. Das mit dem Anfügen eines weiteren Feldes ist nur eine bildiche Vorstellung, um die Funktion einer Turingmaschine einem Nicht-Mathematiker zu vermitteln. In der Tat ist die wahre Turingmaschine aber eine rein mathematische Sache. Und dabei ist das Band einfach eine Abbildung der natürlichen Zahlen (für den einseitigen Fall) oder der ganzen Zahlen (beidseitig unendliches Band) auf das Bandalphabet. Eine solche Abbildung ist ein mathematisches Objekt, eine simple Menge, die selbst unendlich ist (denn es ist ja eine Abbildung einer unendlichen Menge auf eine nichtleere Menge). Das heißt: Sie ist genau wie die Menge der natürlichen Zahlen ->aktual<- unendlich. Kurzum: Das Band ist mathematisch exakt betrachtet aktual unendlich. Und wir müssen hier die mathematische Definition nutzen, denn die Turingmaschine ist nicht das Produkt eines Ingeneurs, sondern eines Mathematikers!

Animation

TM Animation

Ich habe vorhin eine Animation einer Turingmaschine erstellt. Sie arbeitet nach den Regeln die hier im Beispiel angegeben werden. Da ich bisher noch nie bei wikipedia was reingestellt habe, traue ich mich nicht einfach den Artikel zu ändern. Vielleicht macht das jemand von euch besser. Das Bild habe ich schon hochgeladen. http://de.wikipedia.org/wiki/Bild:Turing.gif Die Autoren des Programms JFLAP (welches sich übrigens hervorragend für Turingmaschinen- und Automatensimulation eignet) aus dem ich die Screenshots entnommen habe wünschen jedoch eine Verlinkung mit der Animation.

Würde mich freuen wenn mein erster kleiner Beitrag veröffentlicht würde.

Erstmal vielen Dank für den Beitrag, eine Animation könnte sehr helfen, den Artikel anschaulicher zu machen. Nun zur Kritik:

• Das Band ist sehr klein in der Ecke - und dabei ist es doch eigentlich die Hauptsache. Wenn man das Bild auf eine Grösse reduziert, in dem es im Artikle brauchbar wäre (siehe rechts), ist das Band kaum noch zu erkennen. Man sieht auf den ersten Blick nur den Endlichen Automaten, und zu dem müsste man noch den Zusammenhang erklären.
• Die Animation sollte "geloopt" sein, d.h. die Berechnung sollte nach einer kurzen Pause erneut beginnen. Sonst muss man die Seite neu laden, um das nochmal zu sehen, und das ist nervig (und kommt auch nicht jeder drauf).
• Auf der Bildbeschreibungsseite sollte noch stehen, was denn diese TM berechnet, und wie (Pseudocode?). Das sollte dann auch in der Bildunterschrift erscheinen.
• Man sieht recht deutlich, dass das mit screenshots "abgefilmt" ist - mir ist klar dass das bearbeiten einer Animation fummelig ist, aber vielleicht hilft ja jemand, der sich damit auskennt.
• Allgemeint gibt es oft Probleme, animationen zu skalieren - in diesem Fall funktioniert es anscheinend aber. Für Animationen bietet es sich (anders als bei "normalen" Bildern) an, eine massgeschneiderte, kleine Version (evtl zusätzlich) hochzuladen.
• Dass du die Entwickler des Programms um Erlaubnis gefragt hast, ist geradzu vorbildlich. Ich denke nicht, dass das nichtmal nötig war: ich sehe keine Elemente der GUI, die ausreichend Schöpfungshöhe hätten, als dass es den Programmierern Rechte an dem Screenshot geben würde.

Ich hoffe, ich hab dich jetzt nicht abgeschreckt - wie gesagt, ich fände eine Animation hier prima! Ach ja: wie du das Bild in den Artikel einbinden kannst, siehst du, wenn du die den Wiki-Text dieses Kommentars anschaust. Ich habe den Link zum Bild ganz oben in diesen Abschnitt eingefügt. -- D. Dÿsentrieb ⇌ 01:52, 19. Feb 2006 (CET)

Die Animation habe ich gerade mal neu überarbeitet, und neu hoch geladen. Ich hoffe die Darstellung des Bandes ist jetzt deutlicher. Zwar noch genausogroß (wir wollen ja keine hässlichen Verpixelungen). Sie ist geloopt mit 5 Sekunden Pause. Ich denke durch die jetzige Größe der Animation ist gewährleistet, dass sie auch skaliert noch erkennbar ist. -- Razo 18:26, 19. Feb 2006 (CET)

Ich habe jetzt die Animation mit dem Text des Beispiels verlinkt. Ich hoffe das ist so i.O.

Hi, irgendwie war das Bild noch nicht zu sehen. Ich habe es jetzt mal unter die Tabellen gesetzt. --87.123.38.12 12:17, 20. Feb 2006 (CET)

Noch eine Frage: Jetzt ist es ja so, dass jeder Zustand zwei Bezeichnungen trägt, q_(i-1) und s_i. Da im Beispiel ausschließlich von s_i die Rede ist, wäre es vielleicht ganz schön, wenn statt q_(i-1) dort s_i stehen würde ( 0 < i <= 6 ). Dann könnte man die s_i, die im Augenblick da stehen, wieder rausnehmen.. meinst du das das technisch möglich wäre? --87.123.38.12 12:32, 20. Feb 2006 (CET)

Ich hatte es eigentlich schon so beabsichtigt, dass die Animation nicht direkt in den Artikel eingebunden wurde, sondern nur verlinkt, weil sich das Ding ja die ganze Zeit bewegt. Mich persönlich stört das einwenig in einem Artikeltext.

Ansonsten kann ich mir gerne die nächsten Tage nochmal Zeit nehmen und die Bezeichnungen anpassen. Außerdem dachte ich mir, man könnte das Band über den Automaten setzen, damit es als erstes ins Blickfeld fällt. Razo 15:48, 20. Feb 2006 (CET)

Eine Möglichkeit ist es, den ersten "Frame" der Animation getrennt hochzuladen und im Artikel zu zeigen - im Untertitel könnte dann stehen "Animation ansehen", mit Link auf die Animation. Wie z.B. beim ersten Bild in Julia-Menge -- D. Dÿsentrieb ⇌ 18:37, 20. Feb 2006 (CET)

Mich würde diese Animation schon sehr interesieren. Wo köntne ich sie denn jetzt finden?!

Fehler in der Erläuterung des Beispiels

Im Beispiel der Turingmaschine wird behauptet dass die genannte Turingmaschine mit initial "111" und sonst nur leeren Feldern auf dem band die Anzahl der Einsen verdoppelt (wobei natürlich die 0 in der Mitte stehen bleiben muss). Das ist falsch. Denn diese Maschine benötigt Nullen die sie lesen kann um sie dann zu überschreiben. Also braucht sie als Input z.b "1110000" (darauf folgende Felder sind dann irrelevant). Sprich die Sprache der akzeptierten Wörter wäre L=1^i 0^i+1. (i >= 0)

Null ist das leere Feld und gehört lt. Definition zum Bandalphabet. Die Turingmaschine M aus dem Beispiel kann ein leeres Feld erkennen ('lesen') und je nach Überführungsfunktion weiter verfahren und, wie du sagst, kann sie die leeren Felder (also die Nullen) auch überschreiben. Andererseits gehört die Null aber nicht zum Eingabealphabet; damit wäre es dann falsch zu sagen, die Eingabe müsse 1110000 sein. --87.123.38.12 11:58, 20. Feb 2006 (CET)

Wo wird definiert, dass ein leeres Feld der Null entspricht? Was wäre wenn das Eingabealphabet aus m und n bestünde anstatt aus 0 und 1? Razo 15:52, 20. Feb 2006 (CET)

Oh ich nehme alles zurrück. Siehe Diskussion der Formalen Definition oben. Eingabealphabet ist dann in diesem Fall nur 1 und die 0 entspricht dem leeren Feld. Oder sehe ich da immernoch etwas falsch? Razo

Nein, ich sehe das auch so. Gruss, --87.123.39.78 12:49, 21. Feb 2006 (CET)

Turingmaschine genauso fähig wie der Mensch???

Ich will nicht den Eindruck machen, dass ich mich für intelligenter halte als alle anderen die über das Thema nachgedacht haben und wenn ich mit meiner Behauptung eurer Meinung nach falsch liege so weißt mich doch bitte darauf hin, jedoch ist mir Folgendes aufgefallen:

Am Anfang des Artikels steht, dass die Turingmaschine dieselben (wenn nicht sogar mehr) mathematische Fähigkeiten besitzt wie der Mensch. Desweiteren wird auf das Halteproblem eingegangen, welches von einer Turingmaschine nicht zu lösen ist. Dieses Halteproblem ist uns Menschen jedoch (soweit ich das Problem richtig verstanden habe) allgemein bekannt. Mir fällt dazu ein Beispiel ein bei dem zwei Kinder sich um ein Spielzeug streiten und daran ziehen. Das eine Kind A sagt zu Kind B, dass es erst loslässt wenn Kind B auch loslässt. Da Kind B dies erwidert streiten sie sich eine Zeit lang (bis hierhin wie bei der Turingmaschine). Nach einiger Zeit werden sie jedoch zu einer von (schätzungsweise) zwei möglichen Lösungen kommen:

• Ein Kind wird loslassen und das andere Kind bekommt das Spielzeug
• Beide Kinder einigen sich im selben Moment loszulassen und kein Kind bekommt das Spielzeug

Wie auch immer die Entscheidung ausfällt, beruht sie auf der Erkenntnis, dass die Kinder sich in einer, nicht durch aufeinander folgende Operationen lösbaren, Situation befinden. Die Lösung des Problems beruht also nicht auf dem Besitz des Spielzeugs (bzw. dem Anhalten) an sich, sondern der Erkenntnis, dass man das Spielzeug nicht besitzen kann (bzw. das ein anhalten nicht möglich ist) oder dass eine Lösung nur durch eine zeitgleiche Handlung eintritt. Der Mensch ist in der Lage eine solche Situation zu erkennen und seinen Lösungsbegriff auf das Nichtvorhandensein einer Lösung erweitern (keine Lösung ist auch eine mögliche Lösung des Problems; ähnlich wie eine leere Menge) und daraus die nötigen Schlüsse zu ziehen, sowie Entscheidungen zu treffen. In diesem Gebiet ist der Mensch der Turingmaschine meiner Meinung nach überlegen.

Dein Beispiel beschreibt eher das Deadlock-Problem, weniger das Halteproblem. Ausserdem kannst du eine math. Funktion nicht mit dem Gehirn eines Menschen vergleichen. Ob das menschl. Gehirn mächtiger als eine Turingmaschine ist kann erst beantwortet werden, wenn wir wissen ob das menschl. Gehirn mächtiger als eine Turingmaschine ist ;). (Bis dahin halte ich eine psychologische oder gar philosophische Sicht auf dieses Thema für nicht angebracht) --matrixx 09:29, 28. Jun 2006 (CEST)

was the fuck ist "turingmächtig"??

Mehrere Artikel verlinken diesen Begriff hierher!!

Im Zusammenhang mit Rechenmaschinen (-modellen etc.) soll es wohl bedeuten, dass die Maschine genau die Funktionen berechnen kann, die auch schon von Turingmaschinen berechnet werden können, d.h. nach der Church-Turing-These alle berechenbaren Funktionen.--89.247.68.10 11:06, 1. Okt. 2007 (CEST)

Vielleicht sollte man dort jeweils auf Turing-Vollständigkeit verlinken? Oder auf die Church-Turing-These? --Wutzofant (✉✍) 15:51, 1. Okt. 2007 (CEST)

Also in dieser[6] Liste habe ich keinen änderungsbedürftigen Link gefunden. Ich hab aber mal Turingmächtigkeit - ursprünglich eine Weiterleitung auf Church-Turing-These - auf Turing-Vollständigkeit weitergeleitet. Gruss, --89.247.108.194 10:53, 2. Okt. 2007 (CEST)

Bild

Nur eine Kleinigkeit: Im zweiten Bild von oben (animiert) wird nach jedem Schritt das Band bewegt (L,R,0) - in der Definition und im Beispiel steht L,R,0 aber für die Kopfbewegung. --89.247.121.228 13:06, 2. Jul. 2007 (CEST)

Ich habe die Animation gemacht. Mit bewegtem Lese-Schreib-Kopf sähe es nicht so schön aus - es wäre wegen der variablen Kopfposition schwerer so sehen. Letztendlich ist die konkrete Umsetzung der TM eine Vereinbarungssache. Die TM in der Animation hat auch keinen Endzustand, sondern stoppt bei Aufruf der letzten Adresse. Wenn du möchtest, kannst du ja eine kurze Erläuterung in die Bildlegende schreiben. Ich denke aber, dass das nur verwirren und vom Thema ablenken würde.--stefan 09:57, 31. Okt. 2007 (CET)

Das war nur eine Inkonsistenz die mir so aufgefallen war. Eine Erläuterung in der Bildlegende würde in der Tat nur verwirren. Das mit dem Endzustand war mir noch gar nicht aufgefallen :-) Gruß, --89.247.72.222 01:27, 27. Nov. 2007 (CET)

Der Gegensatz Sprache und Maschine

Die Sprache ist das Urmedium des Menschen. Neben den natürlichen Sprachen gibt seit vielen Jahren auch formale Sprachen, zu denen das Formelsystem der Mathematik und die vielfältigen Ausdrucksweisen der Naturwissenschaften gehören.

Eine Automat bzw. eine Maschine hingegen ist etwas physisch Vorhandenes bzw. Vorstellbares oder Konstruierbares.

Weil hier von der Vorstellung einer physisch existenten Maschine (sie ist m.E. realisierbar) geredet und gedacht wird, ist die TM kein mathematisches oder sprachliches sondern ein physisches Modell! --Jens611 11:25, 22. Aug. 2007 (CEST)

Verstehe ich das richtig?

"Akzeptiert eine Turingmaschine eine Sprache und hält sie zusätzlich bei allen Eingaben, die nicht zu dieser Sprache gehören, so entscheidet die Turingmaschine diese Sprache."

Akzeptiert eine Turingmaschine eine Sprache und haltet zusätzlich bei allen Eingaben die nicht zu dieser Sprache gehören, dann entscheidet sich die Turingmaschine für diese Sprache. --62.203.137.198 23:18, 30. Sep. 2007 (CEST)

Entscheidbar zu sein, ist zunächst mal eine Eigenschaft die eine formale Sprache haben (oder nicht haben) kann. Eine Sprache ist nun genau dann entscheidbar, wenn es eine Turingmaschine M gibt, die zu jeder Eingabe eines Wortes entscheidet, ob dieses Wort zur Sprache L gehört oder nicht. Dazu muss sie in jedem Fall anhalten, denn würde sie nicht anhalten wäre ja unklar ob das Eingabewort nun zu L gehört oder nicht. D.h. eine Turingmaschine entscheidet sich nicht für eine Sprache L, sondern entscheidet die (Zugehörigkeit von Worten zur) Sprache L. Gruss, --89.247.68.10 10:53, 1. Okt. 2007 (CEST)