 Sprachen, in denen Turingmaschine vorkommen |
Shaggz118
unregistriert
 |
|
| Sprachen, in denen Turingmaschine vorkommen |
     |
Meine Frage:
Hey liebe Informatiker,
Ich hätte da mal eine Frage an euch. Undzwar habe ich ein Problem mit Sprachen, welche bestimmte Turingmaschinen akzeptieren sollen.
Um mal genauer zu sein habe ich die Aufgabe zu gucken, welche der folgenden 4 Sprachen Entscheidbar sind.
Die Sprachen sehen wie folgt aus:
1.L={<M>|M ist Entscheider (d.h. stoppt auf jeder Eingabe}
2.L={<M>|M ist eine TM und die Sprache, die von M erkannt wird, ist regulär}
3.L={<M,w,n>| M ist eine TM, die bei Eingabe w nach höchstens n Schritten
stoppt}
4.L={<M,w>| M ist eine TM, die bei Eingabe w nach einer geraden Anzahl von Schritten stoppt}
Denken Sie daran, dass mit einer Turing-Maschine immer eine determinisitsche 1-Band Turing-Maschine gemeint ist.
Meine Ideen:
So. Soweit so gut. Mein Ansatz für z.B. die erste Sprache sieht wie folgt aus:
Wir müssen ja überprüfen ob die Sprache L entscheidbar ist, d.h. die TM die für L angeben muss bei jeder eingegebenen TM M stoppen.
1. Ich konstruiere nun eine 2 Band TM für L. Auf dem Hilfsband wir die TM M simuliert.
2. Die 2 Band TM akzpetiert M genau dann wenn sie ein Entscheider ist, dass heißt sie stoppt.
Soweit so gut. Aber falls M jetzt kein Entscheider ist, also zykelt, dann zykelt unsere TM auch. Also ist die die erste Sprache nicht entscheidbar? Aber falls der Gedanke so richtig ist: Dann wäre die 2te Sprache ja auch nicht entscheidbar und die dritte auch nicht. Lediglich die 3te wäre entscheidbar, da wir hier über n eine feste Grenze definieren.
Oder denke ich ganz falsch?
MFG Shaggz118
|
|
17.12.2012 15:37 |
|
|
Shaggz118
unregistriert
|
|
Ich meine natürlich die 4te ist nicht entscheidbar. Und nicht die 3te.
MFG
|
|
|
17.12.2012 15:40 |
|
|
Shaggz118
unregistriert
|
|
| RE: Sprachen, in denen Turingmaschine vorkommen |
|
Ich merk schon, dass ist vollkommener Quatsch was ich da verzapft habe 
. An die Aufgaben muss ich mit dem Satz von Rice rangehen. Zumindest für 1. und 2..
MFG Shaggz118
|
|
|
17.12.2012 16:29 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hi,
mir fehtl leider momentan die Zeit mich intensiv mit solchen Fragen auseinanderzusetzen.
Hier ein paar Ideen:
Satz von Rice ist gut. Die Frage ist, ob der hier Anwendbar ist. Ich denke bei 1. schon. Bei 2. bin ich mir nicht sicher. Schließlich ist ja bekannt, dass die TM eine reguläre Sprache Akzeptiert. Ich denke man kann hier ausnutzen, dass reg. Sprachen entscheidbar sind.
3. ist trivial. (einfach Schritte zählen und nach max n Schritten anhalten und damit entscheiden)
4. Hier wieder Satz von Rice...
VG,
Karlito
|
|
|
18.12.2012 16:42 |
|
|
Shaggz118
unregistriert
|
|
Jop genauso hab ichs jetzt auch gelöst. Bei der 2 kann man auch den Satz von Rice anwenden hab da auch ein Beispiel für im Internet gefunden.
Somit ist nur die 3 Sprache nicht entscheidbar.
Danke für deine Antwort
MFG Shaggz118
|
|
|
18.12.2012 18:09 |
|
|
Shaggz118
unregistriert
|
|
Eh nur die 3te ist entscheidbar
MFG
|
|
|
18.12.2012 18:10 |
|
|
|
