prim rek fkt < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:17 Fr 19.01.2007 | | Autor: | AriR |
Hey leute
wir haben mal in der volesung folgend funktion definiert:
[mm] \phi(e,x_1,...,x_n)=\begin{cases} \{e\}(x_1,...,x_n), & \mbox{falss } e\in PRI und (e)_1=n \\ 0, & \mbox{sonst }\end{cases}
[/mm]
wobei e die Gödelnummer einer primtivrekursiven funktion sein soll,
[mm] \{e\} [/mm] beschreibt die funktion, die durch die gödelnummer e gegeben ist.
PRI ist die menge aller gödelnummer primitiv rekursiver funktionen
[mm] (e)_1 [/mm] ist die primtiv rekursive dekodierungsfunktion an der stelle 1 welches die stelligkeit von e enthält.
ich hoffe das sind alle angaben, die ich zu der funktion machen sollte.
wir haben nun in der vorlesung mit dem diagonalrgument gezeitgt, dass diese funktion nicht prim.rek. ist, welches mir auch klar geworden ist, was mich jetzt noch irritiert ist, dass man eigentlich für diese funktion einen primtivrekursiven term angeben könnte, woraus aber folgen würde, dass die funktion [mm] \phi [/mm] primtiv rekursiv wäre, welches laut dem diagonalargument nicht möglich ist.
ich versuche den term mal hinzuschreiben, vielleihct liegt der fehler schon dort:
[mm] \phi(e,x_1,...,x_n)=\{e\}(x_1,...,x_n)*sg(\chi_{PRI}(e)\wedge \chi_=((e)_1,n))
[/mm]
[mm] \chi [/mm] ist hierbei die char.fkt von PRI bzw =, welche prim.rek sind.
sg(x)=0 für x=0 und sonst 1.... ist auch prim.rek laut vorlesung
alle funktionen die hier also verwendet werden, sind prim rekersuiv (haben wir in der vorlesung gezeigt)
demnach müsste [mm] \phi [/mm] doch auch primtiv rekursiv sein oder nicht?
ich hoffe einer von euch hat lust mir hier zu helfen :)
Gruß Ari
|
|
| |
|
Moin Ari,
das Problem ist die universelle Funktion:
Du schreibst
[mm] \phi(e,\ldots )=\{e\}(\ldots)\cdot\ldots
[/mm]
und das ist gerade keine primitiv-rek Definition mehr !
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:57 Mi 24.01.2007 | | Autor: | AriR |
meinst du damit, dass das dekodieren von e und die daraus codierte funktion herzuleiten, die e beschreibt nicht mehr primitiv rekursiv ist? ich meine wir hatten aber in der vorlesung bewiesen, dass dies primitiv rekursiv ist. das kann man ja auhc induktiv nach der def. der gödelisierung realtiv leicht machen oder nicht?
hab dich vielleicht falsch verstanden?
|
|
|
| |
|
Moin Ari,
ich meine, dass die primitiv rekursiven Funktionen keine universelle prim. rek. Funktion haben.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 19:45 Mi 24.01.2007 | | Autor: | AriR |
asoo ich glaube ich habe es verstanden, man müsste schon die universelle fkt benutzen für die partiell rekursiven fkt usw..
vielleicht nochmal eine andere frage und zwar wenn man sich die funktion [mm] \phi [/mm] anschaut, kann man das schon irgendwie sehen, dass diese nicht primtiv rekursiv ist oder merkt man dsa nur daran, dass man vergeblich nach einem primitiv rekursiven term such und dsa nicht klappt und man dann versucht zu zeigen, dass diese nicht primitiv rekursiv ist.
ich meine so auf den ersten blick würde ich denke, dass diese funktion primtiv rekursiv ist.
also kann man sich das villeicht irgendwie veranschaulichen?
in dem beweis, wo man widerlegt, dass [mm] \phi [/mm] p.r. ist zeigt man ja sozusagen, dass die funktion, die [mm] \phi [/mm] berrechnet, nicht in der klasse die primitiv rekursiven funktion vorkommt, wenn ich mich nicht irre, kann man das vielleicht auch so sehen, ohne ein diagonalargument?
gruß ari
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Do 01.02.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
