Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Berechenbarkeitstheorie » Erstellen einer Turingmaschine
Druckversion
Druckversion
Autor
Universität/Hochschule J Erstellen einer Turingmaschine
Schutze
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 23.10.2020
Mitteilungen: 35
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-05-08


Ich komme mit einer Aufgabe nicht weiter und erhoffe mir hier eine Hilfestellung bzw. Anregung.



Das ist die erste Aufgabe, die wir bislang zu Turingmaschinen bekommen haben, deshalb bin ich da noch etwas ratlos.

Meine bisherigen Überlegungen sind die Folgenden:

- beginnt meine Eingabe mit einer 0, muss eine 0 folgen
- streicht man die letzten beiden Stellen von B(x), nennen wir das neue
  Wort B'(x), gilt B'(x) = B(y)
- gilt |B(x)| <= 2, muss B(y) = 0 gelten

Ich bin mir nicht sicher, ob davon überhaupt etwas zielführend ist und falls ja, wüsste ich nicht, wie ich das entsprechend umsetze, sodass ich ans Ziel komme.

Vielleicht kann mir ja hier jemand auf die Sprünge helfen. Das ist nicht die erste Aufgabe über der ich heute stundenlang hänge und irgendwann wird es doch etwas frustrierend.

Viele Grüße
 



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6932
Wohnort: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-05-08


Hallo Schutze,

zunächst: Ich habe auch keine Routine beim Entwerfen einer Turingmaschine.

Als erstes würde ich von der Maschine die Mitte des Eingabeworts suchen lassen. Das könnte man machen, indem man den Lesekopf immer abwechselnd nach rechts und links laufen lässt. Dabei ersetzt man links eine 0 durch A und eine 1 durch B. Rechts ersetzt man eine 0 durch C und eine 1 durch D.

Aus
10001010100110
wird so
BAAABABCDCCDDC

Nun ersetzt man das linkste C oder D durch A bzw. B
BAAABABADCCDDC

Jetzt ist schon mal klar, welche Zeichen zu x und welche zu y gehören müssen.

Jetzt vergleicht man nacheinander das linkste A oder B mit dem linksten C bzw D. Bei Erfolg ersetzt man es durch E. Bei Misserfolg bricht die Maschine mit FALSE ab.

BAAABABADCCDDC
EAAABABAECCDDC
EEAABABAEECDDC
EEEABABAEEEDDC
-> FALSE, da im nächsten Schritt A mit D verglichen wird.

Ich hoffe, ich konnte mich einigermaßen verständlich ausdrücken. Der Fall, dass x < 4 muss noch gesondert betrachtet werden.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Schutze
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 23.10.2020
Mitteilungen: 35
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2021-05-08


Hallo StrgAltEntf,

vielen Dank erstmal für deine Antwort. Ich glaube mit dem Tipp komme ich schon ein gutes Stück weiter. Hatte auch überlegt, die Symbole entsprechend zu überschreiben, aber das erstmal wieder verworfen, da ich überhaupt nicht in Betracht gezogen habe, hierfür 4 verschiedene Symbole zu verwenden.

Für heute habe ich mehr Einsen und Nullen gesehen, als mir lieb ist, also gebe ich morgen mal Rückmeldung ob es geklappt hat.

 



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6932
Wohnort: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2021-05-08


Dann viel Erfolg, bin gespannt! Hast du einen Turing-Maschinen-Simulator, oder musst du das alles mit Bleistift und Papier machen?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6850
Wohnort: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2021-05-09


Mal ehrlich, so eine Aufgabe als erstes Beispiel für eine TM zu stellen, bei der man die TM angeben muss, ist Quälerei. Es ist relativ klar, was man machen muss, man braucht aber viele Zustände, um das Verhalten zu beschreiben. Zum einen braucht man mehrere Phasen, wie StrAltEntf schon beschrieben hat, zum anderen muss man auch noch diverse Spezialfälle abfangen,

Noch ein Tipp.
Damit man sich bei den Fällen x<4, y<2 nicht verheddert, bietet es sich an, in einem ersten Durchlauf zu schauen, ob die Zahl höchstens drei Stellen hat, ob die erste Ziffer eine 0 ist und was die letzte Ziffer ist. Dies kann man tun, in dem man mit Hilfe des Zustands "zählt" und "merkt".
Hat die Eingabe eine führende Null, so wird nur akzeptiert, wenn sie aus genau zwei Ziffern besteht und beide 0 sind.
Ist die erste Ziffer eine 1 und hat die Eingabe höchstens drei Ziffern dann akzeptiert man genau dann, wenn die letzte Ziffer eine 0 ist.
Ist die erste Ziffer eine 1 und hat die Eingabe mehr als drei Ziffern dann benutzt man den Anzatz von StrAltEntf.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Schutze
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 23.10.2020
Mitteilungen: 35
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2021-05-09


@StrgAltEntf
Alles mit Stift und Papier. Bin schon froh, ein vernünftiges Tablet zu haben. Das macht es wenigstens möglich, mal eben was zu korrigieren.

@Kitaktus
Finde es ja schon beruhigend, dass ich nicht allein der Meinung bin, dass das irgendwie etwas übertrieben ist. In den Beispielen aus der Vorlesung wurde dann sowas wie a^i b^i durchgespielt und man wird dann ins kalte Wasser geworfen. Wäre ja schön, wenn das dann wenigstens die einzige Aufgabe wäre, an der man Ewigkeiten hängt, aber weit gefehlt. Versuche mich auch eigentlich immer durchzubeißen (bei der Fächerkombination Mathe/Info wohl auch nicht anders machbar), aber bin dann doch froh, dass man hier Hilfe bekommt, wenn man nicht weiter kommt. Also auch an dich vielen Dank für die weiteren Tipps.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6932
Wohnort: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2021-05-09


2021-05-09 09:16 - Schutze in Beitrag No. 5 schreibt:
Alles mit Stift und Papier.

Da beneide ich aber auch den Korrektor nicht, der sich durch die Lösungen kämpfen muss.

Ich halte es für sehr unwahrscheinlich, dass man das auf Anhieb fehlerfrei hinbekommt, ohne es auszuprobieren. Das ist eigentlich bei jeder Programmiersprache so, sobald es etwas komplexer wird. Ich würde daher empfehlen, im Netz nach einer Simulation zu suchen, mit der man seinen Code ausprobieren kann. Auf Anhieb habe ich dieses hier gefunden.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Schutze
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 23.10.2020
Mitteilungen: 35
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2021-05-09


@StrgAltEntf

Da haben die Tutoren das Glück, dass unser Übungsbetrieb etwas anders aufgebaut ist. Wir haben jede Woche 6 Aufgaben und müssen vor den Übungen entsprechend ankreuzen, welche Aufgaben wir bearbeitet haben. In der Übung selbst, muss dann jemand der "zufällig" ausgewählt wird und die Aufgabe angekreuzt hat, das ganze vorstellen und erklären. Von daher bleibt der Aufwand bei den Studenten hängen. Aber das ändert für mich ja sowieso nichts.

Danke für den Tipp mit der Simulation. Ich habe es tatsächlich ohne hinbekommen und anschließend eine Seite gefunden, auf der man seine TM grafisch Stück für Stück aufbauen kann, mit der Möglichkeit anschließend entsprechend Eingaben zu simulieren. Ich hatte vorher gar nicht in Erwägung gezogen, dass es sowas gibt.

Mein Automat hat jetzt stolze 24 Zustände und unzählige Übergänge, wobei ich die Umsetzung der Sonderfälle weniger aufwändig fand, als die der Standardfälle.

Ich poste die fertige TM hier jetzt mal nicht, da ich niemandem den Spaß rauben möchte, die Aufgabe selbst zu erledigen. Die Tipps hier haben auf jeden Fall geholfen.

Falls jemand von den netten Helfern interessiert daran ist, wie die TM denn nun aussieht, lasst es mich gern wissen. Dann schicke ich es per PN.

Viele Grüße



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6932
Wohnort: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2021-05-09


2021-05-09 14:16 - Schutze in Beitrag No. 7 schreibt:
Da haben die Tutoren das Glück, dass unser Übungsbetrieb etwas anders aufgebaut ist. Wir haben jede Woche 6 Aufgaben und müssen vor den Übungen entsprechend ankreuzen, welche Aufgaben wir bearbeitet haben. In der Übung selbst, muss dann jemand der "zufällig" ausgewählt wird und die Aufgabe angekreuzt hat, das ganze vorstellen und erklären. Von daher bleibt der Aufwand bei den Studenten hängen. Aber das ändert für mich ja sowieso nichts.

Wenn das so ist, wirst du dich (wenn du denn ausgelost wirst) wohl darauf beschränken, die Ideen qualitativ wiederzugeben und nicht alle 24 Zustände und die unzähligen Übergänge an die Tafel schreiben. Dem könnte sowieso niemand folgen. Also so ähnlich (und bestimmt schöner wahrscheinlich) wie ich es in #1 gemacht habe.

Viele Grüße
StrgAltEntf



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Schutze
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 23.10.2020
Mitteilungen: 35
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2021-05-10


Ja, wenn man nach gesundem Menschenverstand geht, dann lässt sich so eine Aufgabe wohl weder vernünftig überprüfen noch vorstellen. Nichts desto trotz müssen wir vollständige Ausarbeitungen machen. Aktuell findet ja eh alles nur online statt. Da wird dann die Bearbeitung eben hochgeladen, oder der Bildschirm geteilt und dann darf man anhand seiner Lösung alles erklären. War jetzt in den letzten Wochen das gleiche Spiel, nur mit DEA und NDEA. Die waren ein gutes Stück simpler und selbst da sind Fehler z.T. nicht aufgefallen. Da ich die TM fertig gebastelt habe, kann ich die auch in gewünschtem Maße vorstellen. Finde es eher schade, dass man dann wahrscheinlich nur eben einen Sonderfall durchspielt, der kurz genug zum Vorstellen ist, nachdem man sich damit etliche Stunden auseinandersetzen musste.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Informatik-Rentner
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 29.10.2015
Mitteilungen: 62
Wohnort: Essen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2021-05-10


NUr zur INfo: die akzeptierten Wörter/Zahlen >3 haben alle die Form x00x



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2256
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2021-05-10


2021-05-10 16:44 - Informatik-Rentner in Beitrag No. 10 schreibt:
NUr zur INfo: die akzeptierten Wörter/Zahlen >3 haben alle die Form x00x

Würde sich für $x=7$ (und somit $y=1$) nicht das Wort $\tt 1111$ ergeben?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Schutze
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 23.10.2020
Mitteilungen: 35
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2021-05-10


@zippy,
Das ist richtig. Für x=11 müsste y=2 gelten und die entsprechende Eingabe wäre dann 101110, also auch nicht von der Form xx00xx.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Schutze
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 23.10.2020
Mitteilungen: 35
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, vom Themenstarter, eingetragen 2021-05-13


Ich bräuchte nochmal eure Meinung zu der Aufgabe. Es hat sich für mich herausgestellt, dass die Aufgabe, so wie sie gestellt ist, überhaupt nicht lösbar ist.

Ich kann sagen:
x = 15 und y = 3, somit wäre der String 111111 und soll nach Voraussetzung akzeptiert werden.

Wähle ich x = 7 und y = 7 ist die Voraussetzung offensichtlich nicht erfüllt. Trotzdem führt die Wahl zu dem gleichen String 111111.

Die TM kann ja entweder akzeptieren oder nicht. Das heißt eine Wort, welches nicht in der Sprache liegt, muss akzeptiert werden, damit ein Wort, dass in der Sprache liegt akzeptiert werden kann.

Vielleicht übersehe ich ja hier was, aber meine Argumentation erscheint mir doch hier recht schlüssig.

Viele Grüße




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6932
Wohnort: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2021-05-13


Hallo Schutze,

2021-05-13 18:22 - Schutze in Beitrag No. 13 schreibt:
Wähle ich x = 7 und y = 7 ist die Voraussetzung offensichtlich nicht erfüllt. Trotzdem führt die Wahl zu dem gleichen String 111111.

Das spielt keine Rolle! Es gilt: w ist genau dann ein Wort der Sprache, wenn x und y existieren mit \(y=\lfloor x/4\rfloor\) und w = B(x)B(y).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Schutze
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 23.10.2020
Mitteilungen: 35
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, vom Themenstarter, eingetragen 2021-05-13


Okay, ich verstehe. Also müssen nur die Worte nicht akzeptiert werden, für die keine x,y existieren, sodass die Voraussetzung erfüllt ist.

Viele Dank für die schnelle Antwort.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Schutze hat die Antworten auf ihre/seine Frage gesehen.
Schutze hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]