 |
 |
 |
 |
 |
 |
Startseite » Forum » Turing-Maschine - Wort zum Spiegeln
Turing-Maschine - Wort zum Spiegeln
Universität / Fachhochschule
Sonstiges
Tags: Sonstig
 
|
  |
|---|
|
Hallo Habe Hausaufgaben zu Turingmaschinen zum lösen erhalten. Die Theorie habe ich dazu gelesen, allerdings bei der untenstehenden Aufgabe habe ich bereits Probleme Hier die Aufgabe: "Schreiben Sie eine Turingmaschine, die ein Wort über dem Alphabet spiegelt." Es ist mir unklar, wie ich dazu vorgehen muss. Wenn ich mir Videos/Tutorials zu Turingmaschinen anschaue, dann scheint mir alles plausibel usw, allerdings, keine Ahnung wie ich vorgehen muss. Danke für die Hilfestellung Freundliche Grüsse Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Hallo, wie viel Erfahrung hast du denn mit Automaten und speziell Turing-Maschinen? Wenn die Erfahrung bei Null liegt, wird es hier schwierig. Das Konzept einer Turing-Maschine versucht ja gerade, den Ablauf des Problems quasi mit Stift und Papier nachzubilden. Also: Auf deinem Blatt steht z.b. _100110111001_ ("_" soll anzeigen, dass dort "nichts" steht!) Wie würdest du denn nun die Aufgabe abarbeiten? Bedenke: Je weniger du "Sonderschritte" gehst - bzw. - je mehr du das Algorithmus betrachtest, desto größer die Chancen darauf, diesen in eine Turing-Maschine umzuwandeln. Online kannst du das z.b. auf flaci.com mal ausprobieren. Ich habe eine Turing-Maschine mit 9 Zuständen gefunden. Diese Lösung fand ich ziemlich straight. Mfg Michael |
 |
|
Hallo michaL Das Thema ist mir ziemlich neu. Wenn ich zur Theorie zum Thema lese, ist es ziemlich komplex beschrieben, es gibt sogenannte Turing-Maschinensimulatoren, wo man das ganze mal "durchspielen" kann, scheint auch relativ plausibel zu sein. Aber mit der gestellten Aufgabe, kann ich wenig anfangen.. Muss ich die 0 und in der geschweiften Klammer "ins Band" schreiben? Was lese ich und was schreibe ich? In welch Richtung gehe ich...mit der 0 und 1? Alles Neuland.. Ich habe zudem meinen Dozenten auch noch angeschrieben. Gerade bin ich noch ein Youtube Video über Turinmaschinen mir am anschauen, zum 5ten mal erfahre ich dasselbe, schön und nett, hilft mir allerdings trotzdem nicht um die Aufgabe zu lösen.. Grüsse |
|
|
|
Hallo, also, zunächst geht es um "Wörter". Das ist ein Fachwort. Gemeint ist mit "Wort" eine Zusammensetzung aus den kleinsten Teilen eines Wortes, dem so genannten Alphabet. Klingt bei 0 und 1 eigenartig, aber es geht letztlich um alle endlichen(!) Zusammensetzungen von Nullen und Einsen. Sprich: Du kannst ein Wort über dem Alphabet {0;1} verstehen als eine natürliche Zahl in Binärschreibweise, wobei führende Nullen zugelassen sind (was dann aber die Wörter 0 und 00 als verschieden(!) ausweist). Wie du diese Wörter "verstehst", ist aber nebensächlich. Die Aufgabe besteht darin, ein gegebenes Wort wie etwa 001110010101001010010101 durch die Turing-Maschine umdrehen zu lassen: 101010010100101010011100 (Wenn ich jetzt keinen Fehler gemacht habe.) Um einen Algorithmus zu finden, musst du Teile deiner höheren Hirnfähigkeiten bewusst ausschalten. (Etwa "auf einen Blick" mehrere "Ziffern" gleichzeitig betrachten.) Stelle dir vor, die Eingabe (also irgendein Wort über dem Alphabet {0;1}) z.b. 001110010101001010010101 wäre gegeben. Vor diesem Wort wäre der Bandinhalt leer; danach auch. (Überprüfbar durch ein spezielles Zeichen, etwa "_".) Der "Zeiger" zeigt auf den Beginn der Eingabe, hier also auf die Null ganz links. Wie würdest du das "Wort" umdrehen? (Umdrehen ist übrigens nicht unbedingt so gemeint, dass du die Eingabe veränderst. Du kannst das Eingabewort anfangs erst einmal weitgehend so lassen und erst im Laufe der Zeit und bei Bedarf ändern.) Versuche doch einmal, sprachlich zu beschreiben, wie man das Eingabewort umdrehen könnte. Mfg Michael |
|
|
|
Hallo michaL Ich habe deinen letzten Beitrag zu meiner Frage jetzt etwa 3 mal gelesen und zu verstanden :-))) Also, wenn ich jetzt das richtig verstehe: 1. hast du lediglich als Beispiel genommen (im 2. Abschnitt). Das könnte auch genau so gut. sein?? 2. Zu deine Frage: "Wie würdest du das "Wort" umdrehen?" Ich würde vom Leerzeichen eins nach rechts verschieben, dann lande ich bei "0" ("0"01110010101001010010101) den überschreiben mit "1" dann habe ich "1"01110010101001010010101 Wobei du schreibst, ich soll die Eingabe nicht verändern das heisst genau, das was ich dir jetzt unter Punkt 2 erklärt habe, darf ich nicht tun.... oder? |
|
|
|
Hallo, ja, das ist ein Beispiel. Es könnte auch 0 sein, oder 1 oder 00, 11, 10 oder 01 (usw.). Ich denke, ich habe mich vielleicht immer noch nicht verständlich machen können. Du sollte ein Eingabewort wie 011 "undrehen" zu 110. Wir lesen so ein Wort von links nach rechts. Du sollst das Eingabewort lediglich in umgekehrter Reihenfolge schreiben (s. Beispiel oben). Etwa so: Eingabewort -> Ausgabewort 01 -> 10 11001 -> 10011 USW. Wie würde man da strategisch/algorithmisch drangehen? Ich würde es wie folgt machen: Zu Beginn steht bei der Eingabe 11001 der Schreib-Lese-Kopf auf der linken 1. Ich würde mir (bildlich gesprochen) eine Spiegelmarkierung machen, dann immer so weit nach LINKS wandern, bis ich zu dem noch nicht bearbeiteten Zeichen komme. Das würde ich dann als "bearbeitet" markieren (damit ich beim nächsten "Durchlauf" es nicht noch einmal bearbeite). Dann würde ich ans Ende meiner eigenen Bearbeitung wandern, also nach RECHTS. Dort würde ich - abhängig von dem Zeichen, dass ich eben als bearbeitet markiert habe - am Ende das Zeichen anhängen. Dann würde ich für das nächste Zeichen wieder nach LINKS wandern, bis zum ersten (d.h. am weitesten RECHTS stehenden) unbearbeiteten Zeichen und die Sache geht "von vorne los". Ich schreibe mal die Schritte auf, die der Schreib-Lese-Kopf machen würde. Leeres Band erkenne ich an "_", die Spiegelmarkierung mache ich mit "#". Ein in Bearbeitung befindliches/bearbeitetes Zeichen markiere ich mit "D": Anfangszustand: _11001_ (Erst nach rechts bis zum Ende der Eingabe wandern.) .^ _11001_ ..^ _11001_ ...^ _11001_ ....^ _11001_ .....^ _11001_ ......^ (Ich lese rechtes Ende und mache dort die Spiegelmarkierung.) _11001#_ ......^ (Jetzt wandere ich nach LINKS bis zum ersten 0 oder 1 über alle "D"s hinweg.) _11001#_ .....^ (Erstes unbearbeitetes Zeichen gefunden. Markiere die Bearbeitung! Nach RECHTS) _1100D#_ ......^ _1100D#_ .......^ (Ende meiner eigenen Bearbeitung erreicht. Die 1 schreiben! Dann LINKS) _1100D#1_ ......^ _1100D#1_ .....^ _1100D#1_ ....^ (am weitesten rechts stehendes unbearbeitetes Zeichen. Ab hier wie oben!) _110DD#1_ ....^ _110DD#1_ .....^ _110DD#1_ ......^ _110DD#1_ .......^ _110DD#1_ ........^ (Ende erreicht. Die 0 schreiben. Dann wieder RECHTS bis zum nächsten Zeichen) _110DD#10_ .......^ _110DD#10_ ......^ _110DD#10_ .....^ _110DD#10_ ....^ _110DD#10_ ...^ (Markierung setzen und, dann nach RECHTS bis Ende) _11DDD#10_ ....^ _11DDD#10_ .....^ _11DDD#10_ ......^ _11DDD#10_ .......^ _11DDD#10_ ........^ _11DDD#10_ .........^ (Ende erreicht. Markiertes Zeichen setzen. Dann LINKS! _11DDD#100_ ........^ _11DDD#100_ .......^ _11DDD#100_ ......^ _11DDD#100_ .....^ _11DDD#100_ ....^ _11DDD#100_ ...^ _11DDD#100_ ..^ (Markieren, dann wieder RECHTS!) _1DDDD#100_ ...^ _1DDDD#100_ ....^ _1DDDD#100_ .....^ _1DDDD#100_ ......^ _1DDDD#100_ .......^ _1DDDD#100_ ........^ _1DDDD#100_ .........^ _1DDDD#100_ ..........^ (Markiertes Zeichen setzen. Dann wieder LINKS bis zum nächsten Zeichen.) _1DDDD#1001_ .........^ Ich breche hier mal ab. Es ist nur noch das eine Zeichen zu bearbeiten. Verstehst du, was ich mir dabei gedacht habe? Mfg Michael |
|
|
|
Hallo michaL Ich lese jetzt alles genau durch, sorry war an einem Bewerbungsschreiben dran... habe mich jetzt wieder ans Notebook gesetzt und gerade deine Nacricht gesehen... Besten Dank, das hast ja sehr ausführlich versucht zu erklären! LG Arda |
|
|
|
Ohh jemine, das ist ja kompliziert so auf den ersten Blick....muss das schier ausdrucken und dann Zeile um Zeile durchstudieren... Ich danke dir sehr, was du dir da für Mühe gemacht hast. Scheint schon mal ein Einstieg für den Anfang zu sein. Tausend Dank! |
|
|
|
Kurze Rückfrage: "........^" Das stellt die Verschiebung des Zeigers lediglich dar oder? Ich meine die Punkte "......." |
|
|
|
Hallo, im folgenden findest du den Text einer Datei, die auf flaci.com als json-Datei hochgeladen werden kann. Dort definiert das ganz eine Turing-Maschine, die bei der Eingabe 11001 die entsprechende Folge an Bandinhalten generiert. Außerdem wir die Maschine visualisiert. Mfg Michael PS: Zur Rückfrage: Ja. Inhalt von Automaton_Umkehrer.json : { "name": "Umkehrer", "description": "Kehrt ein {0;1}-Wort um", "type": "TM", "automaton": { "simulationInput": [ "1", "0", "0", "1", "0" ], "Alphabet": [ "0", "1", "#", "D" ], "StackAlphabet": [ "|", "0", "1", "#", "D" ], "States": [ { "ID": 1, "Name": "q0", "x": 120, "y": 290, "Final": false, "Radius": 30, "Transitions": [ { "Source": 1, "Target": 1, "x": 0, "y": -150, "Labels": [ [ "0", "0", "R" ], [ "1", "1", "R" ] ] }, { "Source": 1, "Target": 2, "x": 0, "y": 0, "Labels": [ [ "|", "#", "L" ] ] } ], "Start": true }, { "ID": 2, "Name": "q1", "x": 340, "y": 290, "Final": false, "Radius": 30, "Transitions": [ { "Source": 2, "Target": 2, "x": -60, "y": -140, "Labels": [ [ "D", "D", "L" ] ] }, { "Source": 2, "Target": 3, "x": 0, "y": 0, "Labels": [ [ "0", "D", "R" ] ] }, { "Source": 2, "Target": 6, "x": 0, "y": 0, "Labels": [ [ "1", "D", "R" ] ] }, { "Source": 2, "Target": 9, "x": 0, "y": 0, "Labels": [ [ "|", "|", "R" ] ] } ], "Start": false }, { "ID": 3, "Name": "q2", "x": 490, "y": 200, "Final": false, "Radius": 30, "Transitions": [ { "Source": 3, "Target": 3, "x": 0, "y": -150, "Labels": [ [ "D", "D", "R" ] ] }, { "Source": 3, "Target": 4, "x": 0, "y": 0, "Labels": [ [ "#", "#", "R" ] ] } ], "Start": false }, { "ID": 4, "Name": "q3", "x": 740, "y": 200, "Final": false, "Radius": 30, "Transitions": [ { "Source": 4, "Target": 4, "x": 50, "y": -130, "Labels": [ [ "0", "0", "R" ], [ "1", "1", "R" ] ] }, { "Source": 4, "Target": 5, "x": -10, "y": -60, "Labels": [ [ "|", "0", "L" ] ] } ], "Start": false }, { "ID": 5, "Name": "q4", "x": 440, "y": 50, "Final": false, "Radius": 30, "Transitions": [ { "Source": 5, "Target": 5, "x": -90, "y": 0, "Labels": [ [ "0", "0", "L" ], [ "1", "1", "L" ] ] }, { "Source": 5, "Target": 2, "x": 0, "y": -10, "Labels": [ [ "#", "#", "L" ] ] } ], "Start": false }, { "ID": 6, "Name": "q5", "x": 490, "y": 380, "Final": false, "Radius": 30, "Transitions": [ { "Source": 6, "Target": 6, "x": 0, "y": -150, "Labels": [ [ "D", "D", "R" ] ] }, { "Source": 6, "Target": 7, "x": 0, "y": 0, "Labels": [ [ "#", "#", "R" ] ] } ], "Start": false }, { "ID": 7, "Name": "q6", "x": 740, "y": 380, "Final": false, "Radius": 30, "Transitions": [ { "Source": 7, "Target": 7, "x": 80, "y": -10, "Labels": [ [ "0", "0", "R" ], [ "1", "1", "R" ] ] }, { "Source": 7, "Target": 8, "x": 0, "y": 0, "Labels": [ [ "|", "1", "L" ] ] } ], "Start": false }, { "ID": 8, "Name": "q7", "x": 430, "y": 540, "Final": false, "Radius": 30, "Transitions": [ { "Source": 8, "Target": 2, "x": 0, "y": 0, "Labels": [ [ "#", "#", "L" ] ] }, { "Source": 8, "Target": 8, "x": -170, "y": -10, "Labels": [ [ "0", "0", "L" ], [ "1", "1", "L" ] ] } ], "Start": false }, { "ID": 9, "Name": "q8", "x": 240, "y": 380, "Final": true, "Radius": 30, "Transitions": [ { "Source": 9, "Target": 9, "x": -110, "y": 0, "Labels": [ [ "D", "|", "R" ], [ "#", "|", "R" ] ] } ], "Start": false } ], "lastInputs": [ [ "1", "0", "0", "1", "0" ] ] } } |
|
|
|
super, das probier gleich mal aus. Die json-Datei |
|
|
|
Mit der von dir erstellten json-Datei wirds vieeeeellll verständlicher.... |
 |
|
Perfekt aufgezeigt!!! |
|
|
|
Hallo, die wesentliche Frage ist, ob du jetzt in der Lage wärest, eine ähnlich schwierige/einfache Aufgabe selbst zu lösen? Ist dir (z.B.) klar, warum die Verzweigung bei nötig(!) ist? Könntest du eine Turing-Maschine schreiben, die bei einem {0;1}-Wort erkennt, ob es von links nach rechts gelesen das gleich ist wie das von rechts nach links gelesene (also ob es ein so genanntes Palindrom ist)? Mfg Michael |
|
|
|
Danke. |
1541540
1541265