Begründe Entscheidbarkeit < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Begründen Sie, welches der folgenden Probleme
(i) entscheidbar
(ii) semi-entscheidbar
(iii) nicht semi-entscheidbar ist.
Probleme:
Hier nun 3 Probleme |
Hi!
Die Frage bezieht sich nicht konkret auf die Probleme, sondern eher auf die Aufgabenstellung:
Zuallerst soll ich "begründen", d.h. insbesondere nicht beweisen. Es reicht dann also eine textuelle Beweisidee und muss nicht 100%ig formal sein oder?
Nun zum vorgehen:
Reicht es, um zu zeigen, dass ein Problem (semi)entscheidbar ist, wenn ich ein Schema angebe, wie eine Turingmaschine konstruiert werden kann, die das Problem löst? Alternativ könnte ich natürlich auch eine Reduktion angeben, aber die TM für die konkreten Probleme finde ich hier etwas intuitiver.
Falls ich nun den Verdacht habe, dass das Problem unentscheidbar ist, so sollte ich das nach Möglichkeit mit dem Satz von Rice begründen, oder?
Warum ich hier nun konkret Frage ist, weil die Aufgabenstellung die Überschrift "Satz von Rice" trägt, aber meiner Meinung nach, mit Hilfe des Satzes von Rice nur entschieden werden kann, ob eine Sprache (Problem) nicht entscheidbar ist. Der Satz liefert ja keine Aussage über die (Semi-)Entscheidbarkeit der Sprache.
Gruß
Pille
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:20 Mo 13.06.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
