View Full Version : [FRAGE] - turing maschine
es hat geheissen, dass nach april - sofern prof. salzer dazukommt - eine "gescheite" version des skriptums rauskommt, welche das im threadtitel angedeutete thema besser erläutert!
es hat sich natürlich nichts getan oder ?
darüber weiß ich nix, aber die folien dazu hast eh gfunden oder?
steht eh ne menge drauf..
Meinst du das hier: http://www.logic.at/lvas/thinf1/skriptum/turing.pdf ? Hat er unter Lehrveranstaltungsunterlagen als Ergänzung zum Skriptum gepostet.
Ist, wie ich find, eine ganz nette Ausarbeitung vom Salzer zum Thema, wenn auch nicht unbedingt besonders leicht verständlich.
gut, dann gibts also doch sowas :)
Meinst du das hier: http://www.logic.at/lvas/thinf1/skriptum/turing.pdf ? Hat er unter Lehrveranstaltungsunterlagen als Ergänzung zum Skriptum gepostet.
Ist, wie ich find, eine ganz nette Ausarbeitung vom Salzer zum Thema, wenn auch nicht unbedingt besonders leicht verständlich.
danke, genau das habe ich gesucht ;-)
Ist, wie ich find, eine ganz nette Ausarbeitung vom Salzer zum Thema, wenn auch nicht unbedingt besonders leicht verständlich.
weil alle anderen unterlagen so besonders leicht verständlich sind :))
pinkhippo
01-07-2004, 17:21
kann jemand das ableitung von turing maschine erklären bitteee... kellerautomat verstehe ich schon.. aber diese turing maschine.. blegh* help please...
weil alle anderen unterlagen so besonders leicht verständlich sind :))
Stimmt schon :) Aber ich muss sagen, die Teile die der Salzer geschrieben hat sind allein beim ersten Durchlesen so viel verständlicher und besser erklärt, als das meiste Zeug, das aus Fermüllers Feder stammt. Das gilt halt leider nicht so sehr für die Turing-Maschinen, das hab ich damit gemeint :)
Ableitung von Worten über eine Turing-Maschine? Im Prinzip gehts darum, dass die Zustände angeben, in welche Richtung wir (am Band/Speicher) gehen, links oder rechts. Die Kanten zwischen den Zuständen geben an, welche Symbole über dem Eingabealphabet durch welche Symbole über dem Bandalphabet (das ist das Eingabealphabet plus das Leersymbol der Turing-Maschine, das lustige Kastl) ersetzt werden, bzw welche Symbole einfach übersprungen/überlesen werden.
Steht da z.B. a/X, dann wird ein a vom eingegebenen Wort ersetzt durch ein X. Steht da z.B. a,b,c,Y, dann werden alle Vorkommnisse der Symbole a, b, c und Y übersprungen. In beiden Fällen gilt das natürlich für die jeweilige Leserichtung, die grad ansteht.
Am Anfang und am Ende jeden Wortes steht das Leersymbol der Turingmaschine, das lustige Kastl da.
Kann da jetzt leider keine Beispielableitung angeben, aber schau dir Seite 5 im "Turing-Skriptum" (siehe oben) vom Salzer an. Da stehts.
Die Zahlen, die immer zwischen einzelnen Symbolen stehen, sind die Zustände, in denen die Maschine grad ist. Der Zustand bezieht sich offenbar immer auf das Symbol das in der Ableitung rechts vom Zustand steht. Also 0ab heißt, dass die Maschine grad im Zustand 0 ist und das Symbol a abgearbeitet wird. a1b heißt, dass die Maschine grad im Zustand 1 ist, und das Symbol b abgearbeitet wird. Das ist einfach nur die Notation, damit man sich besser auskennt und leichter tut, wenn man so eine Ableitung auf dem Papier durchführt. (Hat nichts damit zu tun, ob sich der Lesekopf jetzt nach links oder nach rechts bewegt.) Je nachdem, ob in dem Zustand R oder L "steht" (in der grafischen Darstellung) bewegt sich der Lesekopf nach rechts oder links, wird also rechts bzw links weitergelesen.
Tjo...das ist vielleicht mal ein Anfang um das zu verstehen?
aber wenn ich eine Turing Maschine selber zeichnen muss. wie weiß ich dann ob ich nach links oder rechts gehe??
So ein Bsp ist mal zu rübung gekommen. Also immer wenn ich sowas in der Form hab a/X, dann heißt es, dass ich mein a durch ein X ersetzte. Geht es denn aus der Angabe hervor, ab dem wievielten a ich durch ein X ersetze?
Wenn mir jemand helfen kännt wär das lieb, die Zeit wird knapp :D
Du musst da aufgrund der Angabe eine passende Turing-Maschine konstruieren. Da sollst du ein Wort entsprechend der Angabe durchjagen können und die Maschine muss es akzeptieren und terminieren. Wie du das machst bleibt dir überlassen, die Maschine muss nur das tun, was die Angabe verlangt. Grundsätzlich würd ich sagen geht man mal nach rechts los, weil ein Wort von links nach rechts eingelesen wird vom Band eingelesen wird.
Zeichen ersetzt man bei einer Turing-Maschine deswegen, weil sie dadurch erkennen kann, welche Symbole schon abgearbeitet wurden und welche noch nicht. Hat die Maschine zum Beispiel schon alle Symbole des Eingabewortes abgearbeitet kann man sie bis zum Ende des Wortes schicken indem alle ersetzen Zeichen überlesen werden, dort muss dann ein Leersymbol stehen und das sagt der Maschine, dass das Wort fertig abgearbeitet wurde und sie in den Endzustand übergehen, also terminieren kann.
Ist meiner Meinung nach keine sehr triviale Aufgabe, vor allem wenn man nicht viel Zeit dafür hat. An der Maschine, die da zur Übung kam bin ich mit einem Kollegen ziemlich lang gesessen, sicher 2h oder so :) und ganz richtig wars dann auch nicht (ein kleiner Schönheitsfehler). Heißt zwar nichts, weils bestimmt andere Leute gibt, die sowas in 5 Minuten runterzeichnen und auch noch eine Tabelle für die Übertragungsfunktion dazumalen, aber für die Prüfung würd ich fast sagen, dass das zu viel wäre. Aber kann mich irren, bin kein Turing-Profi :) Hoff auch meine Erklärungen stimmen halbwegs.
pinkhippo
01-07-2004, 20:16
oyeee... what a headache.. hmmm...
im stuck in the ableitung im 'Turing-Skriptum'
ich verstehe schon bis [] a X a X 2 []
wie kommt man zum [] a X a 4 X [] ?? und jetzt muss ich dem Bandalphabet nach links lesen??
huhuhuuu.. bitte hilf mir noch mal :D
Nun ja, bei []aXaX2[] bist du im Zustand 2 und das nächste Symbol, das die Maschine sieht ist das Leersymbol. Wir sind also im Zustand 2, lesen das Leersymbol (immer noch nach rechts) und landen damit im Zustand 4! Dieser Zustand zeigt aber shcon in die andere Richtung, der Lesekopf bewegt sich jetzt also von jetzt an nach links.
Auf dem Zustand 4 ist eine Schleife, die die Maschine alle Vorkommnisse von a und X überspringen/überlesen lässt, und so lange nach links geht, bis sie wieder ein Leersymbol findet. Sobald ein solches Leersymbol [] ansteht, geht die Maschine in den Zustand 0 über (das ist die Kante, die mit [] beschriftet ist, und von 4 nach 0 führt) und von da an bewegt sich der Lesekopf wieder nach rechts.
Das Ganze geht quasi von vorne los, Maschine ist im Zustand 0 und es steht ein a an. Vom Zustand 0 aus gelangen wir in den Zustand 1, indem wir das a lesen, rechts (und nicht ersetzen, eben aufgrund der Angabe/Spezifikation für diese Turing-Maschine). Im Zustand 1 überspringen wir nach rechts alle Vorkommnisse von X. Wenn nach dem letzten X ein Leersymbol kommt, dann ist das Wort fertig abgearbeitet, die Maschine liest vom Zustand 1 aus nach rechts das Leersymbol und gelangt damit in den Endzustand 5.
Lesen wir aber vorher ein a vom Zustand 1 aus, dann gehen wir nach rechts, landen im Zustand 2 und haben auf dem Weg von 1 nach 2 das gelesene a durch ein X ersetzt. Tja, jetzt sind wir in 2, immer noch in Richtung rechts unterwegs, und überspringen alle vorkommenden X (das ist die Schleife von 2 nach 2), oder lesen ein weiteres a. Kommt so ein a, dann landen wir in Zustand 3 und überlesen auf dem Weg von 3 nach 3 (wieder eine Schleife) alle X die uns begegnen. Jetzt muss irgendwann wieder ein a kommen, das wir auf dem Weg von 3 nach 2 durch ein X ersetzen. Schon sind wir wieder in 2, und es geht weiter. Und immer weiter. Und weiter. So lange, bis die Maschine von 0 über ein gelesenes a, eine Anzahl gelesener X und ein gelesenes Leersymbol [] in den Endzustand 5 kommt, weil das Wort inzwischen fertig abgearbeitet wurde.
Das wars im Prinzip. Hoffentlich verständlich.
pinkhippo
01-07-2004, 20:51
ahaaa.. jetzt verstehe ich...
thank you very much @ Daff !! very well explained... :applaus: and nice timing :thumb:
Septic.exe
01-07-2004, 20:59
... aber für die Prüfung würd ich fast sagen, dass das zu viel wäre. ...
Dein Wort in Salzer's Ohren *g*.
Dein Wort in Salzer's Ohren *g*.
in der ausarbeitung vom salzer von dem beispiel aus der vorbereitungsstunde steht ja folgender satz:
Der Beweis, dass L nicht regulär ist, entspricht in der Schwierigkeit durchaus, dem was bei den Prüfungen erwartet wird. Der Beweis, dass L nicht kontextfrei ist, sowie die Turing-Maschine sind zwar instruktiv, verlangen aber ein wenig zuiel Genialität.
heißt das, dass turing maschinen nicht kommen, weil sie zu schwer sind, oder das nur für das eine beispiel die turing maschine zu schwer ist?
Also das strange Kastl, das erstmals an 6. Position im Siebentupel oben auf Seite 2 auftaucht, ist ein Symbol und kein fehlendes Zeichen in meinem Schriftsatz?
Ich war mir sicher dass das ein Darstellungsfehler war...
Also das strange Kastl, das erstmals an 6. Position im Siebentupel oben auf Seite 2 auftaucht, ist ein Symbol und kein fehlendes Zeichen in meinem Schriftsatz?
Ich war mir sicher dass das ein Darstellungsfehler war...
nein, das ist das symbol für das leerwort in einer turing maschine. wurde auch so in der vorlesung verwendet
Eh klar.
Wär ja auch viel zu einfach, wenn man sich an Konventionen halten würde und für das Leerwort in Turing-Maschinen das gleiche Symbol verwenden würde wie bei allen anderen Automaten. Hier ausnahmsweise ein Kasterl statt einem Epsilon zu verwenden ist ja auch viel logischer und intutiver, und fördert das Verständnis dieser *leicht* abstrakten Materie sicherlich ungemein.
:hewa::hewa:
Hat bestimmt historische Gründe...das "normale" Leerwort wird auch oft als ein Lamda geschrieben, habs bisher außer beim Salzer noch nicht wirklich als Epsilon geschrieben gesehen. Naja.
Aber was gut dazupassendes: MUAHAHAHA die Griechen haben gewonnen :D Das freut mich als Landsmann natürlich ungemein :) Jetzt kann ich beruhigt weiterlernen. Sorry, off topic :)
ChristofNeutron
02-07-2004, 01:06
Mir ist bei der Turingmaschine ein Licht aufgegangen, wie ich mir das wirklich als Lesekopf über einem Band vorgestellt habe. Also dass die Zahlen genau über dem Zeichen stehen, welches ich gerade lese. Dadurch wird man (werde ich) nicht so sehr verwirrt, was ich als nächstes lesen muss, sonder ich lies einfach dass was darunter steht und verschiebe dann den Schreibkopf in die Richtung die bei meiner nächsten Zahl steht ;)
Plantschkuh!
02-07-2004, 01:31
Aber ich muss sagen, die Teile die der Salzer geschrieben hat sind allein beim ersten Durchlesen so viel verständlicher und besser erklärt, als das meiste Zeug, das aus Fermüllers Feder stammt.
Blinder, unbegründeter Haß ist doch was schönes... Was genau stammt aus Fermüllers Feder? Das Skriptum und die Folien sind alle vom Salzer.
das Leerwort in Turing-Maschinen
Es ist nicht das Leerwort, sondern ein Symbol, das anzeigt, daß das betreffende Feld des Bandes leer ist. Also ein Leersymbol sozusagen. Das ist was anderes.
Blinder, unbegründeter Haß ist doch was schönes... Was genau stammt aus Fermüllers Feder? Das Skriptum und die Folien sind alle vom Salzer.
Hat überhaupt nichts mit Hass zu tun, weder mit blindem, noch mit unbegründetem, noch mit beiden. Keine Ahnung wo du das herauslesen konntest. Hass würde ich eher mit LVAs wie IuG2 beim Steinhardt in Verbindung bringen, aber eigentlich auch nichtmal da, ist es einfach nicht wert. Im Gegenteil, fand ThInf1 echt die interessanteste und gescheiteste Vorlesung dieses Semester. Dass ich mit dem Stoff nicht so gut vertraut bin wie du, und das Gebiet trotz allem immer noch ziemlich neu für mich (und sicher die meisten anderen auch) ist, tut dem keinen Abbruch.
Aber willst du sagen, dass das "C. Fermüller" in "Copyright G. Salzer, C. Fermüller" nur zur Verzierung auf dem Cover des Sriptums steht? Dass der Fermüller für seinen Teil der Vorlesung nur vom Salzer vorgefertigtes Material, sowohl auf den Folien, als auch im Skriptum verwendet? Und dass der Salzer das deswegen nicht vorträgt, obwohl er es doch geschrieben hat, sondern es dem Fermüller überlässt, damit der auch dafür bezahlt wird, eine Vorlesung zu halten? Klingt in meinen Ohren eher unvernünftig, aber du kennst dich offenbar besser aus, kann ja sein.
Aber dann bilde ich mir die Stiländerung vom ersten (über das zweite, da bin ich eher unsicher) zum dritten und vierten Kapitel nur ein? Dass diese Stiländerung mit dem Wechsel der Vortragenden ganz gut zusammenpasst auch? Und auch mit der Art, wie der Fermüller sein Zeug unterrichtet? Kann ja durchaus sein, wenn dem so ist, dann bin ich wohl einem grässlichen Irrtum unterlegen und tue damit dem Fermüller (zumindest was die geschriebenen Teile betrifft) sehr unrecht, was mir leid täte.
Ändert trotzdem nichts daran, dass es ab Kapitel 3 ein sehr knapper, sehr formaler Stil ist, nicht gerade extrem hilfreich im Erarbeiten des Stoffes. Und das Argument, dass komplexe/komplizierte Sachverhalte nur mit komplexer/"formaler" Sprache beschrieben werden können zieht irgendwie nicht, hab neben mir "Induction, Recursion and Programming" von M. Wand liegen (offenbar eine der Vorlagen für das Skriptum), und der schafft es sehr schön, immer wieder ein paar erklärende, sehr hilfreiche Sätze in den Text einzubauen (vor allem den Teil über Syntax und Semantik der AL und die partiellen Korrektheitsaussagen hab ich bei Wand viel besser verstanden, als im Skriptum). Natürlich, das Skriptum ist Begleitmaterial, ersetzt weder VO noch zusätzliche Literatur. Aber im vorderen Teil funktionierts ja auch? Was mich wieder auf meine Annahme bringt, dass es wohl doch Salzer und Fermüller zu zweit sind, nicht Salzer alleine. Aber wie gesagt, irre mich wahrscheinlich, wenn du da besser bescheid weißt.
Plantschkuh!
02-07-2004, 02:57
Aber willst du sagen, dass das "C. Fermüller" in "Copyright G. Salzer, C. Fermüller" nur zur Verzierung auf dem Cover des Sriptums steht? Dass der Fermüller für seinen Teil der Vorlesung nur vom Salzer vorgefertigtes Material, sowohl auf den Folien, als auch im Skriptum verwendet?
Im Prinzip ja auf beides. Das Skriptum ist in dieser Form zwei Jahre alt, damals wurde die Vorlesung rein vom Salzer gehalten, und es ist auch nur Salzer auf dem Skriptum gestanden. (Es ist wohl nicht in völliger Isolation entstanden, aber der Salzer ist der Hauptverfasser, auch von den hinteren Teilen.) Weiters ist die Aufteilung des Stoffs auf die Vortragenden ziemlich willkürlich (ich habe neulich den Fermüller gefragt), vielleicht werden sie in Zukunft auch mal untereinander tauschen.
Es kann schon gut sein, daß du beim Wechsel der Stoffgebiete von den formalen Sprachen zur formalen Verifikation einen Stilbruch wahrnimmst, das liegt aber sicher nicht an einem Autorenwechsel. Ich denke, es liegt echt vor allem daran, daß sich der Stoff grundlegend unterscheidet.
Ich verstehe, dann war ich wohl wirklich etwas daneben mit meiner Annahme, die zwar nicht unbegründet oder weit hergeholt war, trotzdem aber falsch. Schande über mich armen Zweitsemestrigen :)
Hassen tu ich trotzdem nichts, was mit dieser LVA zu tun hat. :) Außer vielleicht die Prüfung heute.
Nun ja, bei []aXaX2[] bist du im Zustand 2 und das nächste Symbol, das die Maschine sieht ist das Leersymbol. Wir sind also im Zustand 2, lesen das Leersymbol (immer noch nach rechts) und landen damit im Zustand 4! Dieser Zustand zeigt aber shcon in die andere Richtung, der Lesekopf bewegt sich jetzt also von jetzt an nach links. ....
.....Lesen wir aber vorher ein a vom Zustand 1 aus, dann gehen wir nach rechts, landen im Zustand 2 und haben auf dem Weg von 1 nach 2 das gelesene a durch ein X ersetzt. Tja, jetzt sind wir in 2, immer noch in Richtung rechts unterwegs, und überspringen alle vorkommenden X (das ist die Schleife von 2 nach 2), oder lesen ein weiteres a. Kommt so ein a, dann landen wir in Zustand 3 und überlesen auf dem Weg von 3 nach 3 (wieder eine Schleife) alle X die uns begegnen. Jetzt muss irgendwann wieder ein a kommen, das wir auf dem Weg von 3 nach 2 durch ein X ersetzen. Schon sind wir wieder in 2, und es geht weiter. Und immer weiter. Und weiter. So lange, bis die Maschine von 0 über ein gelesenes a, eine Anzahl gelesener X und ein gelesenes Leersymbol [] in den Endzustand 5 kommt, weil das Wort inzwischen fertig abgearbeitet wurde.
Das wars im Prinzip. Hoffentlich verständlich.
Ich hätte dazu noch eine Frage, und zwar kommt bei dem Bsp. dann
oaXXXo5 ..... o steht für komisches Kästchen(Leerzeichen)
raus, aber da ist das ganze Wort noch gar nicht abgearbeitet, weil nicht alle
a durch X ersetzt sind. Wieso ist man da schon fertig, oder geht das Wort nicht??
MFG Angel
p.s. wäre nett, wen nkurz jemand antworten könnte!!
Ich hab' mir das angesehen. Also man kann es nicht abarbeiten, weil von Zustand 0 auf 1 um ein a nach Rechts gerückt wird. Es ist unmöglich das erste a zu ersetzen. Daher ist oaxxxo5 der Endzustand, der einzige der deterministisch erreicht werden kann.
Die andere Frage ist, ob das heisst dass der Automat das Wort aaaa nun akzeptiert oder nicht. Ich würde intuitiv annehmen, dass das ganze Prozedere bewiesen hat, dass der Automat dies NICHT tut.
Ich hab' mir das angesehen. Also man kann es nicht abarbeiten, weil von Zustand 0 auf 1 um ein a nach Rechts gerückt wird. Es ist unmöglich das erste a zu ersetzen. Daher ist oaxxxo5 der Endzustand, der einzige der deterministisch erreicht werden kann.
Die andere Frage ist, ob das heisst dass der Automat das Wort aaaa nun akzeptiert oder nicht. Ich würde intuitiv annehmen, dass das ganze Prozedere bewiesen hat, dass der Automat dies NICHT tut.
Hab mir das Beispiel zwar nicht genauer angeschaut, aber wenn in einer Turing-Maschine ein Endzustand erreicht wird, heißt das auch, dass das Wort akzeptiert wird, egal wie das Band noch ausschaut.
Muss ja auch so sein, denn aaaa ist eindeutig in der Sprache a^2n für n=2.
Laut dem Beispiel aus dem Zusatzskript Turingmaschine wird das Wort so akzeptiert. Also ich glaub das Templars antwort stimmt, also muss man mit dem Wort einfach nur den EZ erreichen können.
Naja, is halt so denk ich mal!
Lg ANgel
Na gut, dann so... ^^ Zum Glück ist das heute nicht gekommen...
Es ist nicht das Leerwort, sondern ein Symbol, das anzeigt, daß das betreffende Feld des Bandes leer ist. Also ein Leersymbol sozusagen. Das ist was anderes.
Aaaaasoooo, dieses war mir nicht bewusst. Hab Leerwort und Leersymbol für das gleiche gehalten.:verycool: Danke für den Hinweis.
Die Prüfung hab ich wahrscheinlich trotzdem geschafft, obwohl null Ahnung von Turing und dem gesamten Kapitel 4. Wird mir nächstes Semester bei TheoInf2 wohl gehörig auf den Kopf fallen.
Als "interessanteste und nützlichste LVA" in diesem Semester würd ich allerdings AlgoDat wählen. Aber das sind wohl persönliche Vorlieben, die hier entscheiden...
vBulletin® v3.7.1, Copyright ©2000-2009, Jelsoft Enterprises Ltd.