Frage zum Satz von Rice

jak
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 11. Nov 2004 15:42
Kontaktdaten:

Frage zum Satz von Rice

Beitrag von jak »

Hi.

Ich weiss nicht mehr genau in welcher Klausur ich das gelesen habe aber es wurde gefragt ob man bei dem folgenden Problem den Satz von Rice anwenden kann um zu beweisen, dass es nicht entscheidbar sein kann:

{i in N | Existiert x0 mit phi_i(x0) = x0}

In der Musterloesung wurde ohne Begruendung behauptet, dass hier des Satz von RIce nicht anwendbar waere... ich weiss aber nicht, warum dies nicht der Fall sein sollte.

In einer anderen Klausur wurde erwaehnt, dass man beachten soll, die unerliegende Problemfunktionsmenge abgeschlossen ist unter Komposition. Das ist aber nciht notwendig, um den Satz anzuwenden, korrekt? Ich muss einfach nur zeigen, dass es eine P-berechenbare Funktion gibt, die in der Menge ist und eine die draussen ist und schon bin ich fertig, ist das richtig?

mfg + VIELEN DANK!!!!

jak

erik.tews
Computerversteher
Computerversteher
Beiträge: 326
Registriert: 5. Jan 2004 20:48

Beitrag von erik.tews »

Hallo

Ich denke hier kann man den Satz von Rice anwenden, x0 soll irgendeine beliebige Variable sein, und nicht irgendwie von i abhängen, oder?

Die Menge muss auch nicht bezüglich komposition abgeschlossen sein. Z. B. wenn lediglich die Funktion f(x) = x*x enthalten ist, ist der Satz von Rice anwendbar, die Menge ist aber nicht bezüglich komposition abgeschlossen da f(f(x)) = x*x*x*x nicht in ihr enthalten ist.

Simon Siegler
Computerversteher
Computerversteher
Beiträge: 369
Registriert: 16. Apr 2007 09:12

Beitrag von Simon Siegler »

Diese Lösung und auch die Aufgabenstellung würde ich mir gerne mal ansehen. Wenn Sie also vielleicht doch noch herausfinden können, um welche Klausur es sich handelt, würde ich mich über diese Information freuen.

Der Satz von Rice liefert die Nicht-Entscheidbarkeit von Indexmengen zu nicht-trivialen Mengen berechenbarer Funktionen. Anwendbar ist er also, wenn die zu untersuchende Menge M eine Indexmenge zu einer Menge berechenbarer Funktionen F ist und F nicht alle berechenbaren Funktionen enthält, aber auch nicht leer ist.
Diese Kriterien scheinen von der gegebenen Menge erfüllt zu sein.

Auf die Menge \(\{i\in\mathbb{N}\,|\,\exists x_0\in\mathbb{N}.\,\varphi_i(x_0)=i\}\) hingegen ist der Satz von Rice nicht anwendbar.

HTH

michael2k5
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 117
Registriert: 2. Dez 2005 19:22
Wohnort: Darmstadt-Eberstadt
Kontaktdaten:

Beitrag von michael2k5 »

als kleiner tipp vielleicht noch: ich prüfe folgendermaßen, ob es sich bei M um eine indexmenge handelt...

sei i in M und gelte phi_i = phi_e
wenn hieraus folgt, dass e auch in M ist, dann hast du eine indexmenge.
das wars eigentlich schon ^^

Simon Siegler
Computerversteher
Computerversteher
Beiträge: 369
Registriert: 16. Apr 2007 09:12

Beitrag von Simon Siegler »

Das trifft ziemlich genau die Definition des Begriffs "Indexmenge".

michael2k5
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 117
Registriert: 2. Dez 2005 19:22
Wohnort: Darmstadt-Eberstadt
Kontaktdaten:

Beitrag von michael2k5 »

ich bin eben die klausuren von prof walther auch nochmal durchgegangen.
die menge {i in N | Existiert x0 mit phi_i(x0) = x0} hab ich dabei nicht gefunden. allerdings taucht {i in N | Existiert x0 mit phi_i(x0) = i} in infc-herbst-01-inf4-auf.pdf (aufgabe 5) auf.

jak
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 11. Nov 2004 15:42
Kontaktdaten:

Beitrag von jak »

ah ja, genau das meinte ich... wieso ist die antwort darauf "nein, das kann nicht mit dem satz von rice wiederlegt werden"?

mfg

jak

Simon Siegler
Computerversteher
Computerversteher
Beiträge: 369
Registriert: 16. Apr 2007 09:12

Beitrag von Simon Siegler »

Die Menge ist keine Indexmenge. In Abhängigkeit der gewählten Kodierung lässt sich sicherlich ein Programm schreiben, dass konstant seine eigene Codenummer ausgibt. Sei \(k\) diese Nummer, dann gibt es unendlich viele Programme, die die Funktion \(C^1_k\) berechnen. Davon ist nur eines in der Menge enthalten.

Antworten

Zurück zu „Archiv“