Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Satz von Rice
Hi,
eine kleine, moeglicherweise auch dumme, Frage zum Satz von Rice:
Im Beweis sprechen wir von der Menge
Prog(S) = {<M> | M berechnet die Funktion f \in S}
Im weiteren ist dann die Rede von der Menge Prog(\emptyset), die durch Syntaxanalyse entscheidbar ist.
Prog(\emptyset) = {<M> | M berechnet die Funktion f \in \emptyset}Da es kein f gibt muesste, meiner Logik nach, Prog(\emptyset) = \emptyset sein.
Allerdings wurde auch (von einem Kommilitonen) schon behauptet, dass Prog(\emptyset) den ganzen Muell enthalten wuerde.
Sollte ich richtig liegen: Fuer was brauch ich dann die Syntaxanalyse (-> oder bezieht die sich nur auf Prog(R) ?)?
Liegt mein Kommilitone richtig: Wie geht das aus der Definition hervor?
-chris
Wenn ich von Prog(\emptyset) nach Prog(S), S \neq \emptyset, gehe, kommen ja Funktionen dazu - gleichzeitig müsste dann aber der ganze „Müll“ rausfallen, sonst wäre Prog(R) = {0,1}*. Das „Rausfallen“ wäre meiner Meinung nach inkonsistent, aber eine eine Bestätigung wäre hier hilfreich.
Vote Prog(\emptyset) = \emptyset.
Da brauchts kein Vote dafür, nach Definition:
Prog(∅) = { | M berechnet eine Funktion f ∈ ∅}
Mit ∀x:x∉∅ folgt:
Prog(∅) = ∅
Edit: Muss auch so sein, sonst bräuchte es die Forderung S≠∅ im Satz von Rice nicht.