sat von rice menge der gödelnr < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:33 Mi 07.02.2007 | | Autor: | AriR |
hey leute
müsste nach dem satz von rice die menge aller gödelnummern primitiv rekursiver funktionen nicht entscheidbar also nicht rekursiv sein?
wir haben in der vorlesung gezeigt, dass die die menge aller gödelnummern primtiv rekursiver funktionen wieder primitiv rekursiv ist, aber das ist doch ein widerspruch zum satz von rice oder nicht?
gruß ari
|
|
| |
|
Moin Ari,
erstmal ein Lob, Du machst Dir Gedanken, das ist gut so, wenn Du die Sachen so hinterfragst, wirst Du weiterkommen !
Zur Frage:
Was sagt der Satz von Rice genau ?
Nimm eine Teilmenge C von [mm] F_{\mu}, [/mm] der Menge der [mm] \mu [/mm] - rekursiven Funktionen mit
[mm] \emptyset\subsetneq C\subsetneq F_{\mu}.
[/mm]
Dann ist die Menge
[mm] \{x|\:\varphi_x\in C\} [/mm] nicht rekursiv entscheidbar.
Wenn Du [mm] C=F_{\prim} [/mm] betrachtest, ist zwar die Menge aller x, die primitiv-rekursive Herleitungen von [mm] f\in F_{prim}
[/mm]
codieren, entscheidbar, aber es gibt ja zu [mm] f\in F_{prim} [/mm] auch Definitionen mit [mm] \mu-Operator, [/mm] und die
Menge
[mm] \{x|\:\varphi_x\in F_{prim} \}
[/mm]
beinhaltet also sozusagen insbesondere auch das Entscheidungsproblem zu einem beliebigen x,
ob es zu [mm] f=\varphi_x [/mm] auch eine primitiv-rek. Herleitung gibt.
Also: Kein Widerspruch. 
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:54 Do 08.02.2007 | | Autor: | AriR |
vielen dank schonmla für deine antwort,
wenn ich das richtige verstehe, beinhaltet die menge, die man betrachtet, um den satz von rice anzuwenden, mehr elemente, als wirlich nur die gödelnummern der primitiv rekursiven funktionen.
ich meine verstanden zu haben, dass das die funktionen sind, die mit dem [mm] \mu [/mm] operator definiert wurden.
aber diese sind ja gar nicht primitv rekursiv oder?
das wären dann ja gerade die [mm] \mu [/mm] partiellen funktionen, und wenn man sich die indizes dieser funktionen anschaut, kann man den satz von rice doch gar nicht anwenden.
ich denke mal ich hab dich irgendwie falsch verstanden +g+
siehst du irgendwo den verständnisfehler? :)
Gruß und nochmalls danke...
|
|
|
| |
|
Moin Ari,
es gibt Funktionen, die primitiv rekursiv sind, die man aber auch mit dem [mm] \mu-Operator [/mm] definieren kann.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 16:09 Fr 09.02.2007 | | Autor: | AriR |
aber nur mit dem beschränkten oder nicht? wenn man den unbeschränken nimmt, dann ist dies doch nicht mehr abgeschlossen in den prim. rek fkt oder?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Mi 14.02.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
