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)
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
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
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 und die Bildmenge der Übergangsfunktion endlich. Damit muss die Turingmaschine, wenn sie nicht hält, irgendwann wieder auf ein Tupel aus 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)
Kleine Änderungen an der Formalen Definition
In disem Artikel stand in der Formalen Definiton das: das endliche Eingabealphabet sei, dieses halte ich für falsch, geanuso wie: 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 das endliche Eingabealphabet heißen (allso das leere Feld mit einbeziehen). Daraus folgt dann, dass die zweite Definiton nicht möglich ist, da dann gleich 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 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 . Das hat auch einen guten Grund: ist das Eingabealphabet, und 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 gefüllt ist. Wenn jetzt Teil des Eingabealphabets ist, dann ist ja gar nicht klar, was jetzt das Eingabewort ist, etwa "Wort" oder " Wort "...? Natürlich soll die Turingmaschine Zeichen löschen können, dafür muss aber nicht Teil des Eingabe- sondern nur des Bandalphabets sein. Das ist ja aber durch gesagt.
- Also, ich habe den Artikel dementsprechend (zurück) geändert.
Gruß --eo !? 23:10, 1. Dez 2005 (CET)
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.
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.