Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Berechenbarkeitstheorie » Turingmaschine Simulation
Druckversion
Druckversion
Autor
Universität/Hochschule J Turingmaschine Simulation
Chrispyk
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 01.09.2020
Mitteilungen: 14
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-03-07


Guten Tag, ich hätte gerne Hilfe bei folgender Aufgabenstellung



Meine Idee ist jedes Zeichen der Eingabe durch ein Blank zu trennen und die beliebigen Zeichen des zu simulierenden Eingabealphabets durch Zeichenfolgen mit n >= 2 Zeichen zu kodieren. Das Ende des Programmes wird durch zwei aufeinanderfolgende B erkannt.

Das Einsetzen der Trennzeichen ist von der Eingabe abhängig also O(n).
Jetzt muss ich noch herausfinden, wie das einfügen von neuen Zeichen sich auf die Laufzeit auswirkt, da Bereiche auch noch umkopiert werden müssen.
Nun hat mein Dozent gesagt, dass die Schranke komplett von der Eingabe abhängen soll, aber je nach dem wie viele Zeichen das zu simulierende Bandalphabet hat, wird der Zeitverlust größer oder nicht?
Wie kann ich den Zeitverlust herausfinden?



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: 6820
Wohnort: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-03-08


Vorweg: Überlege mal, ob die Angabe O(n) korrekt ist. Wie fügst Du in eine Eingabe mit tausend Nullen und Einsen 999 Blanks ein, wenn Du nur ein Band zur Verfügung hast?
Wenn Du die Aufgabe in O(n) lösen kannst, dann schreibe auf, wie Du das machst!

Ja natürlich, der tatsächliche Zeitbedarf hängt von der Größe des Bandalphabets ab. Die Buchstaben dieses Alphabets müssen ja durch Nullen und Einsen (und evtl. Blanks) kodiert werden. Je größer das Bandalphabet, desto mehr Zeichen sind notwendig.
So wie ich den Dozenten verstehe, interessiert er sich aber hauptsächlich für die Abhängigkeit von der Eingabelänge. Da die Größe des Bandalphabets fest ist und nicht von der Eingabelänge abhängt, schlägt sich der Mehraufwand eventuell nur in einem konstanten Faktor wieder, der dann bei der O-Notation keine Rolle mehr spielt.

Vielleicht hilft es die Frage umzuformulieren:
Angenommen, wir haben statt eines Bandalphabetes mit $2^k$ Buchstaben nur die Buchstaben {0,1,B} zur Verfügung und können dafür ein Band verwenden, dass mit Hilfe von Blanks in lauter Blöcke der Länge k unterteilt ist, wobei jeder Block zur Codierung eines Buchstabens des Original-Alphabetes verwendet wird. Können wir den zeitlichen Mehraufwand dann auf einen Faktor beschränken, der zwar von k abhängt, aber nicht von der Eingabelänge?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Chrispyk
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 01.09.2020
Mitteilungen: 14
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2021-03-10


Vielen Dank, dein Tipp die Zeichen in Blöcke von konstanter Länge zu kodieren macht die Sache einfacher. Mein Denkfehler war die Länge der Blöcke unterschiedlich zu machen und bin nicht darauf gekommen wie der Zeitverlust durch verschieben oder ändern von Zeichen bei Blöcken unterschiedlicher Länge aussieht.

Also wird TM M
BB 01abc BB

Durch TM M' simuliert
BB 000 B 001 B 010 B 011 B 100 BB

statt
BB 0 B 1 B 00 B 01 B 10 BB

\(O((\lceil log_2(k-1)\rceil + 1) \cdot n)\)





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: 6820
Wohnort: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2021-03-10


Ja, soweit die Grundidee.

Es fehlen noch zwei Schritte:
1) Wie lange braucht man, um das Eingabeband zu umzuschreiben, dass man eine Blockstruktur hat. Hier befürchte ich, dass das nicht in Linearzeit geht!
2) Kann ich eine TM mit größerem Arbeitsalphabet so ohne weiteres simulieren? Die neue TM liest ja immer nur ein Zeichen und nicht den ganzen Block. Welche Ideen brauche ich dazu?
3) Um wieviel langsamer ist die zweite TM? Konstanter Faktor? Irgendein Faktor, der mit der Eingabelänge zunimmt?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Chrispyk
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 01.09.2020
Mitteilungen: 14
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2021-03-11


1. Initialisierung:
Die TM hat n Zeichen als Eingabe und muss für jedes Zeichen einen Block von der Größe log(k) schreiben. Also muss die TM n mal über n * log(k) Zeichen gehen. Da log(k) als konstanter Faktor vernachlässigbar ist:
\(O(n^2)\)?
Wenn alle Blöcke geschrieben wurden, steht der Schreib/Lese-Kopf an der linkesten Position der Blöcke und kann mit der Simulation beginnen.

2. Ich erweitere den Zustandsraum \(Q := Q_M \times Q_{M'} \) und die Zustandsüberführungsfunktion \(\delta(\Gamma \times Q_M \times Q_{M'}) = \Gamma \times Q_M' \times Q_{M'}' \times D_M \times D_{M'}\)

Der Kopf geht einmal über den ersten Block und ändert den Zustand \(Q_{M'}\) und die Richtung für die nächste Position \(D'\). Nun ist der Kopf auf dem rechten Blank des ersten Blockes. Falls nötig geht der Kopf noch einmal über den ersten Block und ändert das kodierte Zeichen. Jetzt weiß die TM durch \(D'\) in welche Richtung sich der Kopf bewegen muss und geht dementsprechend zum nächsten Block oder bleibt an der Position.
Der Zeitverlust ist \(O(log(k) \cdot n) \rightarrow O(n)\)

Ich hab das Gefühl, dass ich das zu kompliziert gemacht habe, gibt es eventuell eine einfachere Möglichkeit?



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: 6820
Wohnort: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2021-03-11


Das sieht schon gut aus.

Eine Bemerkung vorweg: Du benutzt k anscheinend für die Anzahl der Zeichen des Bandalphabetes. Bei mir ist k die Länge des Blocks zur Codierung dieser Zeichen, also in etwa der Logarithmus von Deinem k.
Ich behalte die Bezeichnung bei und hoffe, dass das nicht zu Verwechslungen führt.

Das Band vorzubereiten braucht tatsächlich $O(n^2)$ Zeit. Ich wäre zumindest überrascht, wenn es schneller geht. Das Problem ist, dass man mehr Platz braucht. Den kann man sich nur schaffen, indem man den gesamten Bandinhalt nach rechts (oder links) schiebt. Man kann in einem Durchlauf zwar auch mehrere Zeichen um mehrere Stellen verschieben, aber immer nur konstant viele Zeichen um konstant viele Stellen, so dass man $O(n)$ Blöcke $O(n)$-mal verschieben muss.

Die Verarbeitung danach ist dagegen einfach. Richtig, der Trick besteht darin, den Zustandsraum zu erweitern. Steht man am linken Ende eines Blockes der Länge k (k ist fest), dann wechselt man in einen "Lese"-Zustand, läuft einmal zum rechten Ende und merkt sich unterwegs alle Zeichen, in dem man in einen entsprechenden Zustand wechselt. Ist man am Ende angekommen, wird der Zustandswechsel der ursprünglichen TM nachvollzogen (Was muss geschrieben werden und wohin wird gewechselt). Beide Informationen "merkt" man sich wieder, indem man in einen entsprechenden Zustand wechselt. Dann läuft man einmal nach links, befüllt alle Zellen passend und macht am Ende den Schritt zum Block nach rechts bzw. links.
Aus einem Lesen-Schreiben-Bewegen-Schritt sind jetzt ungefähr 3k-Stück geworden, aber da k fest ist, ist das nur ein konstanter Faktor.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Chrispyk
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 01.09.2020
Mitteilungen: 14
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2021-03-11


Vielen Dank, das war sehr hilfreich!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Chrispyk hat die Antworten auf ihre/seine Frage gesehen.
Chrispyk 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]