blatt#5

[wurstus]

hallo,

ich hab keine ahnung wie ich das aktuelle blatt lösen soll.
kann mir jemand von euch eventuell einen anhaltspunkt geben, wie
das z.b. bei aufgabe 1 zu zeigen ist?


greez patrick

[Tankwart]

Um zu zeigen dass ein Problem entscheidbar ist, reicht's ja eine beliebige TM zu finden, die das entscheidet. Ich hab mir überlegt was die Bedingungen für die gegebenen Sprachen sind bzw. was für eine Besonderheit der Graph der DFA's haben muss, um unendliche Sprachen bzw. beliebige Sprachen zu akzeptieren. Dann hab ich Schritt für Schritt aufgeschrieben wie die TM funktioniert, also z.B. "1. Überprüfe ob <M> einen endl. Automaten kodiert und wenn nicht, lehne ab. 2. ...".
Danach hab ich noch erklärt warum das so geht und warum die TM immer terminiert.
So ähnlich ist das Ganze auch im Sipser aufgebaut (Kapitel 4), ich hoff mal das reicht und ist nicht zu schwammig.

2 hab ich noch nicht angefangen.

[Thomy]

@Tankwart: Der 1. Schritt in deinem Beispiel ist übrigens nicht erforderlich, da man davon ausgehen darf, dass die Gödelnummern endliche deterministische Automaten kodieren (siehe Vorlesungsforum). Ich fand es anfangs auch verwirrend, dass diese Bedingung nochmal in der Beschreibung der Sprache (des Problems) drinnen ist.

Aufgabe 2 habe ich auch noch nicht und wäre sehr dankbar für einen Hinweis, wie ich diese Probleme auf die schon bekannten reduzieren soll. Bis jetzt hat noch nichts funktioniert...

MfG
Thomy

[DavidHume]

Aufgabe 2 habe ich auch noch nicht und wäre sehr dankbar für einen Hinweis, wie ich diese Probleme auf die schon bekannten reduzieren soll...

Aye... Umgekehrt, also schon bekanntes Problem auf dieses Problem reduzieren

[Johann]

Ich glaube die 2a) lässt sich durch Reduktion auf das Halteproblem lösen. Es ist nicht entscheidbar ob eine gegebene Turingmaschine ein gegebenes Wort akzeptiert (wohl aber semi-entscheidbar). Nehmen wir an, das ginge, dann würden wir eine Turingmachine bauen, die einfach das Wort durch M jagt, umdreht und nochmal durch M jagt. Aber da das "durch M jagen" schon nicht entscheidbar ist, kann auch das allgemeine gegebene Problem nicht entscheidbar sein. Ich bin allerdings noch nicht so ganz im Klaren über alles, wenn ich falsch liege, bitte korrigieren.

2b) läuft ziemlich sicher darauf hinaus, dass Chomsky 0 unter Komplementbildung nicht abgeschlossen ist. Will heißen: Komplement ist nicht Turing-entscheidbar ergo nicht entscheidbar. (<- Edit: Ich glaub das hilft nicht so viel )


Hier jetzt mal meine Ansätze, wer keine Lösung will (hoffentlich sind welche dabei ), nicht lesen

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

Zur 1.1: Da tu ich mich schwer. Eine unendliche Sprache die von einem DFA erkannt wird beinhaltet ja quasi, dass der DFA einen Zyklus erhält. Soll ich mir da jetzt echt eine TM ausdenken, die Zyklen in Graphen erkennt? Laut Sipser ist unser Verständnis von Algorithmus äquivalent zu "Es gibt eine TM dafür", und da Zyklensuche algorithmisch lösbar ist, würde ich fast genau das hinschreiben: Gibt einen Algorithmus, also gibts ne TM, als entscheidbar?
Edit: Die Aufgabe steht im Sipser, gleiche Idee, ganz andere Ausführung

1.2 Da hab ich mir überlegt, was einen DFA ausmacht, der S* (Sigma, ich muss Latex lernen) akzeptiert. Meine Idee ist, dass ein solcher Automat nur akzeptierende Zustände hat, also Q = F, und das per TM lösen ist ja möglich, also entscheidbar

[colajunkie]

zu 1.2: ist Sigma* nicht ne unendliche Sprache?

[Tankwart]

Jo, aber wenn man nur akzeptierende Zustände hat kann man ja eingeben was man will und es wird akzeptiert.