Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Turing-Maschine - Wort zum Spiegeln

Turing-Maschine - Wort zum Spiegeln

Universität / Fachhochschule

Sonstiges

Tags: Sonstig

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
Laie-und-Stud051983

Laie-und-Stud051983 aktiv_icon

18:52 Uhr, 30.08.2021

Antworten
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 {0,1} 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."
Antwort
michaL

michaL aktiv_icon

20:08 Uhr, 30.08.2021

Antworten
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

Laie-und-Stud051983

Laie-und-Stud051983 aktiv_icon

20:15 Uhr, 30.08.2021

Antworten
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 1 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
Antwort
michaL

michaL aktiv_icon

20:58 Uhr, 30.08.2021

Antworten
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
Laie-und-Stud051983

Laie-und-Stud051983 aktiv_icon

21:13 Uhr, 30.08.2021

Antworten
Hallo michaL

Ich habe deinen letzten Beitrag zu meiner Frage jetzt etwa 3 mal gelesen und zu 80% verstanden :-)))

Also, wenn ich jetzt das richtig verstehe:
1. 001110010101001010010101 hast du lediglich als Beispiel genommen (im 2. Abschnitt).
Das könnte auch genau so gut. 00001110100101001010 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?




Antwort
michaL

michaL aktiv_icon

21:55 Uhr, 30.08.2021

Antworten
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

Laie-und-Stud051983

Laie-und-Stud051983 aktiv_icon

22:15 Uhr, 30.08.2021

Antworten
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
Laie-und-Stud051983

Laie-und-Stud051983 aktiv_icon

22:25 Uhr, 30.08.2021

Antworten
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!
Laie-und-Stud051983

Laie-und-Stud051983 aktiv_icon

22:38 Uhr, 30.08.2021

Antworten
Kurze Rückfrage: "........^" - Das stellt die Verschiebung des Zeigers lediglich dar oder? Ich meine die Punkte "......."
Antwort
michaL

michaL aktiv_icon

22:40 Uhr, 30.08.2021

Antworten
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"
]
]
}
}
Laie-und-Stud051983

Laie-und-Stud051983 aktiv_icon

22:44 Uhr, 30.08.2021

Antworten
super, das probier gleich mal aus. Die json-Datei
Laie-und-Stud051983

Laie-und-Stud051983 aktiv_icon

22:59 Uhr, 30.08.2021

Antworten
Mit der von dir erstellten json-Datei wirds vieeeeellll verständlicher....
Frage beantwortet
Laie-und-Stud051983

Laie-und-Stud051983 aktiv_icon

23:08 Uhr, 30.08.2021

Antworten
Perfekt aufgezeigt!!!
Antwort
michaL

michaL aktiv_icon

07:36 Uhr, 31.08.2021

Antworten
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 q1 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
Frage beantwortet
Laie-und-Stud051983

Laie-und-Stud051983 aktiv_icon

21:08 Uhr, 13.09.2021

Antworten
Danke.