primtive rek. zeigen < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:30 Di 28.11.2006 | | Autor: | AriR |
hey leute,
wir hatten in der vorlesung definiert, dass eine funktion [mm] f:\IN\to\IN [/mm] genau dann primtiv rekursiv ist, wenn sie einen primtiv rekursiven funktionsterm interpretiert.
dabei hat der proffessor noch deutlich erwähnt, dass man niemals per induktion zeigen kann, dass eine funktion prim rekursiv ist, da man sonst nur für jeden eingabewert eine spezielle funktion betrachtet, welche meist prim rekursiv sind, aber die funktion als ganze wieder nicht primtiv rekursiv sein muss.
meine frag ist jetzt,
man könnte ja eine gegebene funktion f auch folgenden term immer angeben.
f(1)= [mm] C^1_{k_1} [/mm] (wobei [mm] C^n_k(x_1,...,x_n)=k [/mm] für alle x)
[mm] f(2)=C^1_{k_2}
[/mm]
.
.
.
usw
das könnte man ja bei jeder funktion machen und die konstanten funktion sind ja alle prim rekursiv, aber genau das würde man ja auch per induktion machen, was ja laut prof falsch ist.
ist dies jetzt falsch, weil man unendlich viele eingabeparameter hat und man somit nie einen vollständigen primtiv rekursiven term angeben kann?
wenn ja, dann sind auf jeden alle funktionen f primtiv rekursiv, wenn sie aber einer gewissen schranke einen konstanten funktionswert annehmen oder?
wäre nett, wenn ihr mir da weiterhelfen könntet.
Gruß ari
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:05 Di 28.11.2006 | | Autor: | moudi |
> hey leute,
>
> wir hatten in der vorlesung definiert, dass eine funktion
> [mm]f:\IN\to\IN[/mm] genau dann primtiv rekursiv ist, wenn sie einen
> primtiv rekursiven funktionsterm interpretiert.
>
> dabei hat der proffessor noch deutlich erwähnt, dass man
> niemals per induktion zeigen kann, dass eine funktion prim
> rekursiv ist, da man sonst nur für jeden eingabewert eine
> spezielle funktion betrachtet, welche meist prim rekursiv
> sind, aber die funktion als ganze wieder nicht primtiv
> rekursiv sein muss.
>
> meine frag ist jetzt,
>
> man könnte ja eine gegebene funktion f auch folgenden term
> immer angeben.
> f(1)= [mm]C^1_{k_1}[/mm] (wobei [mm]C^n_k(x_1,...,x_n)=k[/mm] für alle x)
> [mm]f(2)=C^1_{k_2}[/mm]
> .
> .
> .
> usw
>
> das könnte man ja bei jeder funktion machen und die
> konstanten funktion sind ja alle prim rekursiv, aber genau
> das würde man ja auch per induktion machen, was ja laut
> prof falsch ist.
>
> ist dies jetzt falsch, weil man unendlich viele
> eingabeparameter hat und man somit nie einen vollständigen
> primtiv rekursiven term angeben kann?
![[ok]](/images/smileys/ok.gif "[ok]")
Eine Fallunterscheidung darf immer nur endlich viele Fälle haben.
>
> wenn ja, dann sind auf jeden alle funktionen f primtiv
> rekursiv, wenn sie aber einer gewissen schranke einen
> konstanten funktionswert annehmen oder?
>
> wäre nett, wenn ihr mir da weiterhelfen könntet.
gern geschehen
mfG Moudi
>
> Gruß ari
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:29 Mo 04.12.2006 | | Autor: | AriR |
jo besten dank für die hilfe
|
|
|
|
