Diskussion:Turingmaschine

aus Wikipedia, der freien Enzyklopädie

Inhaltsverzeichnis 1 Frage zu Ausdruck 2 Brainfuck 3 Erklärung für Nicht-Informatiker 4 Der Fehler im Artikel Turingmaschine muss raus! 5 fleißiger Biber 6 "Halteproblem" 7 Fragen 7.1 Was heißt schreiben ? 8 Endlosschleife 9 Luecke in der Schlussfolgerung 10 Kleine Änderungen an der Formalen Definition 11 Unendlichkeit und das Halteproblem 12 Animation 13 Fehler in der Erläuterung des Beispiels 14 Turingmaschine genauso fähig wie der Mensch???

[Bearbeiten] 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)

[Bearbeiten] 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)

[Bearbeiten] 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.

[Bearbeiten] 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)

[Bearbeiten] 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)

[Bearbeiten] "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.

[Bearbeiten] Fragen

[Bearbeiten] 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)

[Bearbeiten] 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)

[Bearbeiten] 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!

[Bearbeiten] 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)

[Bearbeiten] 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!

[Bearbeiten] 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)

[Bearbeiten] 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)

[Bearbeiten] 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)