Hallo liebe Liebenden!

Ich murxe schon seit einigen Stunden auf der Aufgabe 4.2 des aktuellen Aufgabenzettels herum!

Verfluchte Kiste (*bekreuz*), wie fange ich die Aufgabe richtig an?

Hat jemand von Euch eine Idee? Reicht es eigentlich aus, dass ich versuche zu beweisen, dass das Problem entscheidbar ist? Und wenn der Beweis fehl schlägt, dann heisst das, dass das Problem _nicht_ entscheidbar ist, oder? Darf idh das so angehen?

Mein Ansatz ist der, dass ich nachweise, dass die charakteristische Funktion berechenbar ist (ich versuche es immerhin).

Es wäre nett, wenn einer hier mal den Ansatz posten könnte.

Viele Male Danke und liebe Grüße
-Saverio


(edit Slater: möglichst Vorlesung (F1 oder F3) im Titel angeben)
(@slater: Danke für Dein Edit, hast natürlich Recht!)

Ohne jetzt die konkrete Aufgabe zu kennen:

Reicht es eigentlich aus, dass ich versuche zu beweisen, dass das Problem entscheidbar ist? Und wenn der Beweis fehl schlägt, dann heisst das, dass das Problem _nicht_ entscheidbar ist, oder?

Nein, das reicht nicht. Das heisst dann nur, dass der eine Ansatz nicht funktioniert. Andere Ansätze könnten funktionieren.

Siehe http://www.informatik.uni-hamburg.de/TGI/lehre/vl/WS0405/F3/F3-slides3-071-096.pdf
oder Skript, und zwar das Halteproblem: H = {cod(M)cod(w) | TM M hält auf w};

(edit Slater:
Rest zensiert, möglichst keine ganzen Lösungen posten, egal ob korrekt oder nicht,
Zusammenfassung: lässt sich mit dem Halteproblem kombinieren)

Frage an Slater: Muss das so hart zensiert werden? Ich meine, man behauptet hier nicht, daß hier die richtige Lösung ist, aber man will auch die Gegenargumente hören und anderen Lösungen sehen.

tja, muss nicht,
aber in meinen Augen ist das Forum hier nicht zum öffentlichen Austausch von Lösungen/ konkreten Lösungsideen gedacht,
(bis zum Abgabetermin scheinplichtiger Übungen, danach/ sonst gerne)



Diskussionen wie
'hat das mit dem Halteproblem zu tun?'
'naja, bedenke doch Seite xy im Skript'
'achso'
wäre ja noch auf Gespräch-mit-Übungsleiter-Niveau,

aber
'das ist soundso, daraus folgt nach Satz a und Lemma z die Behauptung'
geht mir doch ein wenig zu weit ;)



was kann ich sonst noch dazu antworten?

http://www.fb18.de/cgi-bin/faq.cgi?2003111019644&40
Letzter Abschnitt..

aber
'das ist soundso, daraus folgt nach Satz a und Lemma z die Behauptung'
geht mir doch ein wenig zu weit ;)

Richtig, spaetestens da muss die Grenze gezogen werden. Der Poster selbst hat sich dann zwar die Muehe gemacht (und dabei gelernt), aber nimmt dabei anderen die Moeglichkeit (und Pflicht), sich unvoreingenommen an der Aufgabe zu versuchen.