Turingmaschine < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:03 Do 11.12.2008 | | Autor: | Yas |
Hallo zusammen,
Ich habe diese Frage als uebung bekommen:
Kann jemand mir hilfen um nur die anfang des antwort oder den weg zu finden um diese frage zu beantworten???
Frage:
Betrachten Sie eine alternative Definition der Turingmaschine: Eine TM M ist ein 7-Tupel
M = (S,E,A, SIGMA, s0, BLANK, F), dabei ist
SIGMA : (S \ F) × A → P(S × (A ∪ {L,R})), und die Übergangsrelation ⊢ ist definiert durch:
[mm]a_1[/mm]. . .[mm]a_msb_1b_2. . .b_n[/mm] ⊢ [mm]a_1. . .a_m[/mm]s′[mm]b_1[/mm]′[mm]b_2. . .b_n[/mm] falls (s′, [mm]b_1[/mm]′) ∈ SIGMA(s, [mm]b_1[/mm])
und
[mm]a_1. . .a_msb_1b_2. . .b_n[/mm]⊢[mm]a_1. . .a_mb_1[/mm]s′[mm]b_2. . .b_n[/mm] falls (s′,R) ∈ SIGMA(s, [mm]b_1[/mm])
bzw.
[mm]a_1. . .a_{m-1} a_msb_1. . .b_n[/mm] ⊢ [mm]a_1. . .a_{m-1}[/mm]s′[mm]a_mb_1. . .b_n[/mm] falls (s′, L) ∈ SIGMA(s, [mm]b_1[/mm])
alle anderen Komponenten sind identisch zur bekannten TM definiert
Im Unterschied zur bekannten TM kann die hier so definierte Maschine in einem Arbeitsschritt (Konfigurationswechsel) entweder ein Feld auf dem Band manipulieren oder ein Bewegung ausführen (aber nicht beides).
Zeigen Sie, dass die beiden Modelle äquivalent sind.
dankeeeee!!!!
|
|
| |
|
Hallo Yas,
das klingt interessant und ich würde Dir gern weiterhelfen. Dass Deine Anfrage schon über drei Stunden unbeantwortet herumliegt, lässt mich vermuten, dass ich nicht der einzige bin, der hier ein bisschen ratlos ist.
Schön, Ihr habt also Formelrepräsentationen und Abkürzungen eingeführt. Bei weitem nicht alle davon sind mir begegnet, als ich mich einst mit Turingmaschinen beschäftigte (da war T.Rex noch nicht einmal in Planung).
Kannst Du vielleicht ein paar der Kürzel auflösen? Vielleicht verstehe ich dann besser, was die Frage impliziert, und finde womöglich sogar einen Ansatz.
Falls jemand diese Erläuterungen nicht braucht, lerne ich aber auch gern aus einer informativen Antwort.
Liebe Grüße,
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:35 Fr 12.12.2008 | | Autor: | bazzzty |
Lieber Reverend,
bitte nicht übel nehmen, aber ich muss kurz anmerken, dass ich Yas' Frage schon beantwortet hätte, wenn sie noch als "offen" aufgeführt worden wäre. Es gibt extra den Status "Mitteilung", wenn man mit einer Reaktion die Frage nicht beantwortet, das wäre in dem Fall hilfreich gewesen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:07 Fr 12.12.2008 | | Autor: | reverend |
Hallo Bazzty,
ich bin sicher, dass ich trotz "Antwort" unten eingestellt habe "Frage bleibt unbeantwortet", gerade weil meins ja nur eine Nachfrage war.
Die Statusgeschichte gibt an, dass ich um 00:32h begonnen habe, dazu zu schreiben, und um 00:36h abgeschickt habe, mit der Folge, dass die Frage weiterhin "statuslos" geführt wurde, also rot blieb, offen.
Inwiefern ist dann also eine Mitteilung besser? Denn eine Mitteilung habe ich nicht geschickt, sondern eine Nachfrage.
Liebe Grüße,
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:17 Fr 12.12.2008 | | Autor: | Herby |
Hallo Reverend,
> Hallo Bazzty,
>
> ich bin sicher, dass ich trotz "Antwort" unten eingestellt
> habe "Frage bleibt unbeantwortet", gerade weil meins ja nur
> eine Nachfrage war.
>
> Die Statusgeschichte gibt an, dass ich um 00:32h begonnen
> habe, dazu zu schreiben, und um 00:36h abgeschickt habe,
> mit der Folge, dass die Frage weiterhin "statuslos" geführt
> wurde, also rot blieb, offen.
ja, blieb sie auch - habe ich mit eigenen Äuglein gesehen ![[eek]](/images/smileys/eek.gif "[eek]")
> Inwiefern ist dann also eine Mitteilung besser? Denn eine
> Mitteilung habe ich nicht geschickt, sondern eine
> Nachfrage.
Ich schreibe in solchen Fällen auch eine Antwort, dass ein anderer User erkennt: Aha, da tut sich schon was. Zusätzlich vermerke ich im Feld "Betreff": Rückfrage und vor dem Absenden stelle ich ebenso auf "statuslos" und zusätzlich in meinem Bereich "das soll eine Mitteilung sein".
Liebe Grüße
Herby
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:39 Fr 12.12.2008 | | Autor: | bazzzty |
> > Die Statusgeschichte gibt an, dass ich um 00:32h begonnen
> > habe, dazu zu schreiben, und um 00:36h abgeschickt habe,
> > mit der Folge, dass die Frage weiterhin "statuslos" geführt
> > wurde, also rot blieb, offen.
>
> ja, blieb sie auch - habe ich mit eigenen Äuglein gesehen
>
Bei mir wurde sie als beantwortet geführt. Ich habe extra meine Antwort zur Mitteilung degradiert. Eigentlich sollte die Frage dann doch jetzt wieder offen sein, oder? Sie ist aber, so wie ich sie vorfand: Beantwortet.
>
> > Inwiefern ist dann also eine Mitteilung besser? Denn eine
> > Mitteilung habe ich nicht geschickt, sondern eine
> > Nachfrage.
>
> Ich schreibe in solchen Fällen auch eine Antwort, dass ein
> anderer User erkennt: Aha, da tut sich schon was.
> Zusätzlich vermerke ich im Feld "Betreff": Rückfrage und
> vor dem Absenden stelle ich ebenso auf "statuslos" und
> zusätzlich in meinem Bereich "das soll eine Mitteilung
> sein".
Ist das dann ein Bug? Die Frage war beantwortet, wie auch jetzt wieder, und zwar offenbar aufgrund von Reverends Antwort, nicht erst seit meiner.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:20 Fr 12.12.2008 | | Autor: | reverend |
> Bei mir wurde sie als beantwortet geführt. Ich habe extra
> meine Antwort zur Mitteilung degradiert. Eigentlich sollte
> die Frage dann doch jetzt wieder offen sein, oder? Sie ist
> aber, so wie ich sie vorfand: Beantwortet.
Das ist allerdings (bisher) so und ist mir auch schon passiert. Wenn Du eine Antwort zur Mitteilung herabstufst, wird der Status der Frage nicht wieder auf "offen" gesetzt.
Das wäre dann doch noch ein Wunsch an die Programmierung des Forums.
> Ist das dann ein Bug? Die Frage war beantwortet, wie auch
> jetzt wieder, und zwar offenbar aufgrund von Reverends
> Antwort, nicht erst seit meiner.
Das ist vielleicht nicht mehr rekonstruierbar, ansonsten siehe oben.
@Herby: soll ich Marc dazu mal anfunken?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:37 Fr 12.12.2008 | | Autor: | bazzzty |
> Hallo Bazzty,
>
> ich bin sicher, dass ich trotz "Antwort" unten eingestellt
> habe "Frage bleibt unbeantwortet", gerade weil meins ja nur
> eine Nachfrage war.
Dann tut es mir leid, und der Fehler liegt woanders. Tatsache ist, daß Deine Antwort dazu geführt hat, daß die Frage (auch wenn irgendwo statuslos steht) als grün und beantwortet in der Übersicht geführt wird. Ich habe meine Antwort mutwillig zur Mitteilung degradiert - trotzdem steht da "beantwortet" und Deine Antwort ist als Antwort markiert.
> Die Statusgeschichte gibt an, dass ich um 00:32h begonnen
> habe, dazu zu schreiben, und um 00:36h abgeschickt habe,
> mit der Folge, dass die Frage weiterhin "statuslos" geführt
> wurde, also rot blieb, offen.
Das stimmt, ich habe mir die Statusgeschichte angesehen. Aber die Frage war nicht mehr rot. So wie jetzt, wo ich meine Antwort zur Mitteilung zurückgestuft habe, ist die Frage knallgrün.
> Inwiefern ist dann also eine Mitteilung besser? Denn eine
> Mitteilung habe ich nicht geschickt, sondern eine
> Nachfrage.
Ich vermute da einen Bug, wie gesagt, ich hatte nur beobachtet, daß die Frage als beantwortet markiert war, und das offenbar wegen Deiner Antwort. Eine Mitteilung hätte den Effekt sicher nicht gehabt, aber das ist natürlich nicht Deine Schuld.
Liebe Grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:48 Fr 12.12.2008 | | Autor: | bazzzty |
Das hier ist ja der Kern der Frage:
> Im Unterschied zur bekannten TM kann die hier so
> definierte Maschine in einem Arbeitsschritt
> (Konfigurationswechsel) entweder ein Feld auf dem Band
> manipulieren oder ein Bewegung ausführen (aber nicht
> beides).
> Zeigen Sie, dass die beiden Modelle äquivalent sind.
Zunächst: Äquivalent heißt, daß es zu jeder Maschine aus dem alten Modell eine Maschine im neuen Modell gibt, die das gleiche leistet (die gleiche Sprache erkennt) und umgekehrt. Der Beweis hat also zwei Teile.
Der zweite sollte Dir leicht fallen: Wenn Du eine Maschine hast, die in jedem Schritt nur entweder manipuliert oder bewegt, dann ist das ja im alten Modell nicht verboten.
Zu zeigen ist also, daß es zu jeder Maschine, die in einem Schritt sowohl manipulieren als auch bewegen darf, eine Maschine gibt, die nur eins von beidem tut. Und das ist nicht so schwer: Stell Dir mal vor, Du hast so eine Maschine und willst diese doppelten Aktionen loswerden! Wie schaffst Du es, daß die Maschine in so einem Fall erst manipuliert und sich dann bewegt? Tipp: Du brauchst dazu zusätzliche Zustände, und zwar insgesamt im schlimmsten Fall dreimal soviele wie vorher!
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 17:26 Mo 15.12.2008 | | Autor: | Yas |
vielen dank bazzzty,
also ich habe auch gedacht das liegt an zustaende. Ich habe ueberlegt:
Im allten Moedelle, haben wir L, R und N. Jetzt haben wir bewegung nur nach rechts und nach links, gut Ich habe gedacht, dass wir neue endzustand generieren (ich weis es nicht wie ;) )wenn eine alphabet kommt und wir muessen nichts machen ( N beim allten Modelle) was muss man machen mit der neue Modell? also gehen wir zu Neue zustand und nach Rechts bis die neue Endzustand , dann wieder nach Rechts zu die richtige endzustand?
wie kann ich das formalieren?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:43 Di 16.12.2008 | | Autor: | bazzzty |
> vielen dank bazzzty,
> also ich habe auch gedacht das liegt an zustaende. Ich
> habe ueberlegt:
> Im allten Moedelle, haben wir L, R und N. Jetzt haben wir
> bewegung nur nach rechts und nach links, gut
Moment. Das Problem ist doch, daß wir im alten Modell etwas verändern konnten, und uns dann bewegt haben (in einem Schritt). Jetzt können wir das nicht in einem Schritt. Wenn wir etwas verändern, dann müssen wir in dem Zustand kodieren, wie wir uns im nächsten Schritt bewegen wollen.
> Ich habe
> gedacht, dass wir neue endzustand generieren (ich weis es
> nicht wie ;) )wenn eine alphabet kommt und wir muessen
> nichts machen ( N beim allten Modelle) was muss man machen
> mit der neue Modell?
Ich verstehe die Frage nicht.
> also gehen wir zu Neue zustand und
> nach Rechts bis die neue Endzustand , dann wieder nach
> Rechts zu die richtige endzustand?
Die leider auch nicht. Ist Dir klar, was das Problem ist?
Die "alte" Turingmaschine hat in jedem Schritt das Band manipuliert und sich dann bewegt.
Die "neue" Maschine darf nicht mehr beides inm selben Schritt machen. An dieser Stelle muss man sich behelfen: Wo die alte Maschine beides machen wollte, muß man jetzt die Bewegung im Zustand kodieren. Besser kann ich es nicht erklären.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 13:05 Di 16.12.2008 | | Autor: | Yas |
ja, aber wenn eine eingabe kommt und die TM nicht machen soll (stehen bleiben im alten modell), dann wie ist das in Neue TM???
oder, ist das ueberhaupt wichtig?
> Moment. Das Problem ist doch, daß wir im alten Modell etwas
> verändern konnten, und uns dann bewegt haben (in einem
> Schritt). Jetzt können wir das nicht in einem Schritt. Wenn
> wir etwas verändern, dann müssen wir in dem Zustand
> kodieren, wie wir uns im nächsten Schritt bewegen wollen.
Ich habe die Problem schon verstanden, aber formalierung ist meine problem :(
Also, ich mache dann ein zustand fuer Manipulation, ne andere zustand fuer Rechts und eine fuer Links bewegung. So habe ich genau die alte TM. aber wie ist das formal???
sorry, wenn ich dich genervt hab.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:20 Mi 17.12.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:43 Mi 17.12.2008 | | Autor: | bazzzty |
> ja, aber wenn eine eingabe kommt und die TM nicht machen
> soll (stehen bleiben im alten modell), dann wie ist das > in Neue TM???
> oder, ist das ueberhaupt wichtig?
> Nein, dann bleibt einfach alles beim alten.
> Ich habe die Problem schon verstanden, aber formalierung
> ist meine problem :(
> Also, ich mache dann ein zustand fuer Manipulation, ne
> andere zustand fuer Rechts und eine fuer Links bewegung. > So habe ich genau die alte TM. aber wie ist das formal???
> sorry, wenn ich dich genervt hab.
Nein, Du hast nicht genervt, ich war mir nur nicht sicher, ob wir vom gleichen Problem sprechen.
Die Formalisierung sieht einfach so aus:
Sei TM eine Turingmaschine im alten Modell mit Zuständen S.
Dann konstruieren wir eine neue Turingmaschine TM', die nie in einem Takt manipuliert und sich bewegt wie folgt:
Für jeden Zustand [mm] $s\in [/mm] S$ haben wir drei Zustände in $S'$, nämlich $s$ selbst, [mm] $s_L$ [/mm] und [mm] $s_R$.
[/mm]
Die Übergangsfunktion wird jetzt so definiert, daß
* wenn TM sich in einem Zustand $s$ und einer Eingabe $a$ nur bewegt und in Zustand $s'$ wechselt, dann tut $TM'$ dasselbe.
* wenn TM in einem Zustand $s$ bei einer Eingabe $a$ das Band zu $a'$ verändert, sich nach links bewegt, und in Zustand $s'$ wechselt, dann verändert $TM'$ in dieser Situation das Band nur und wechselt in den Zustand $s'_L$.
(dasselbe gilt für rechts)
* wenn $TM'$ in einem Zustand [mm] $s_L$ [/mm] ist, bewegt sie sich unabhängig vom Bandinhalt um eins nach links und wechselt in den Zustand $s$.
Das ist schon das ganze Geheimnis. Man kann das noch stärker formalisieren, aber dann verliert man den Blick fürs Wesentliche.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:42 Mi 17.12.2008 | | Autor: | Yas |
vielen dank!! Ich habe Meine Uebungs blatt gestern schon abgegeben, meine formalisierung ist einbisschen anders ;) deine bestimmt besser...
Idee war das selbe ... das war aber 100% durch deine grosse hilfe als du mir die Frage schoen erklehrt :)
danke!
|
|
|
|
