partielle Rekursivität < Sonstiges < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:48 Mo 05.07.2010 | | Autor: | Lovelace |
| Aufgabe | Zeigen Sie, dass die folgenden Funktionen partiell rekursiv ist.
(a) f : N → N mit
f(m) = [mm] \begin{cases} \wurzel{m}, & \mbox{für } \wurzel{m} Element \mbox{ N} \\ undefiniert, & \mbox{für } sonst \end{cases}
[/mm]
|
Guten morgen liebe Mathe-Raum-Mitglieder!
ich habe diese Aufgabe auch im Mathe-logik Bereich gepostet, allerdings habe ich das Gefühl, meine Frage ist irgendwie nicht ganz klar...
Inzwischen habe ich in unserem Skript nun auch einen Hinweis gefunden, nach dem die oben genannte Funktion f partiell rekursiv sei mittels [mm] g:N²\to [/mm] N mit g(n, m) = |n²-m|, sodass gilt [mm] \mu [/mm] g(m)= f(m)
Ich glaube, ich weiß auch, wie ich zeigen kann, dass g(n, m) primitiv rekursiv ist, da ich mittels der modifizierten Differenz zeigen kann, dass |n-m| primitiv rekursiv ist, wobei sich aus n ja mittels multiplikation dann ja auch leicht n² machen lässt.
Jetzt allerdings häng ich. Kann mir vllt jemand einen kleinen Schubs von der Leitung geben?!
Viele Grüße, und danke schonmal,
Ada
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
https://vorhilfe.de/read?t=698316
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:24 Mo 05.07.2010 | | Autor: | felixf |
Moin Ada!
> Zeigen Sie, dass die folgenden Funktionen partiell rekursiv
> ist.
> (a) f : N → N mit
> f(m) = [mm]\begin{cases} \wurzel{m}, & \mbox{für } \wurzel{m} Element \mbox{ N} \\ undefiniert, & \mbox{für } sonst \end{cases}[/mm]
>
> Guten morgen liebe Mathe-Raum-Mitglieder!
>
> ich habe diese Aufgabe auch im Mathe-logik Bereich
> gepostet, allerdings habe ich das Gefühl, meine Frage ist
> irgendwie nicht ganz klar...
>
> Inzwischen habe ich in unserem Skript nun auch einen
> Hinweis gefunden, nach dem die oben genannte Funktion f
> partiell rekursiv sei mittels [mm]g:N^2\to[/mm] N mit g(n, m) =
> [mm] |n^2-m|, [/mm] sodass gilt [mm]\mu[/mm] g(m)= f(m)
Genau. (Bei euch ist [mm] $\mu$ [/mm] andersherum definiert als ![[]](/images/popup.gif) hier.)
> Ich glaube, ich weiß auch, wie ich zeigen kann, dass g(n,
> m) primitiv rekursiv ist, da ich mittels der modifizierten
> Differenz zeigen kann, dass |n-m| primitiv rekursiv ist,
> wobei sich aus n ja mittels multiplikation dann ja auch
> leicht n² machen lässt.
Genau.
> Jetzt allerdings häng ich. Kann mir vllt jemand einen
> kleinen Schubs von der Leitung geben?!
Du bist doch fertig. Du hast gezeigt:
* die Funktion $g(n, m)$ ist primitiv rekursiv
* damit ist auch $f(m) = [mm] \mu [/mm] g(n, m)$ primitiv rekursiv
Oder ist dir der erste Punkt noch nicht ganz klar?
> https://matheraum.de/read?t=698316
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:08 Mo 05.07.2010 | | Autor: | Lovelace |
hallo Felix,
das ist ja mal ne gute Nachricht, dass ich einfach fertig sein soll?! Aber ehrlich gesagt...geblickt habe ich das jetzt nicht...ich glaube das Problem ist, dass ich einfach nicht verstehe, was dieser µ-Operator soll!
Immerhin ist mir der Zusammenhang zwischen g(m) und f(m) inzwischen einigermaßen klar geworden. ich gehe praktisch durch die funktion f(m)= |n²-m| alle Quadratzahlen durch und teste so, ob auch m eine Quadratzahl ist (dann wäre ja f(m)= 0 )
Ich hoffe, ich habe das jetzt richtig verstanden...
Liebe Grüße,
Ada
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:23 Mo 05.07.2010 | | Autor: | felixf |
Moin Ada,
> das ist ja mal ne gute Nachricht, dass ich einfach fertig
> sein soll?! Aber ehrlich gesagt...geblickt habe ich das
> jetzt nicht...ich glaube das Problem ist, dass ich einfach
> nicht verstehe, was dieser µ-Operator soll!
der [mm] $\mu$-Operator [/mm] ist eine WHILE-Schleife, die so lange durchlaeuft, bis sie einen undefinierten Wert findet oder eine "Nullstelle".
> Immerhin ist mir der Zusammenhang zwischen g(m) und f(m)
> inzwischen einigermaßen klar geworden. ich gehe praktisch
> durch die funktion f(m)= |n²-m| alle Quadratzahlen durch
> und teste so, ob auch m eine Quadratzahl ist (dann wäre ja
> f(m)= 0 )
Nicht ganz, du gehst alle natuerlichen Zahlen durch und schaust, ob ihr Quadrat gleich $m$ ist. Ist dies fuer ein $n$ der Fall, so ist $g(n, m) = 0$ und der [mm] $\mu$-Operator [/mm] gibt $n$ zurueck. Wird das nie der Fall, ist der [mm] $\mu$-Operator [/mm] undefiniert -- also genau das was du haben willst.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:22 Mo 05.07.2010 | | Autor: | Lovelace |
| Aufgabe | Zeigen Sie, dass die folgenden Funktionen partiell rekursiv ist.
g : N → N mit
g(m) = [mm] \begin{cases} log_2m, & \mbox{für }\wurzel{m} \in N \mbox{ \inN} \\ undefiniert, & \mbox{sonst } \end{cases} [/mm] |
Hallo!
Diese Teilaufgabe müsste sich ja dann analog zu Aufgabenteil 1 lösen lassen, indem ich die Funktion f(m)= [mm] |2^n-m| [/mm] betrachte, beweise, dass diese primitiv rekursiv ist, was wir in der Vorlesung bereits sowohl für Additions- als auch für Exponentialfunktionen bewiesen haben. Und daraus kann ich dann folgern , dass µf(m)= g(m), d.h. g(m) ist partiell rekursiv.
Mein Problem ist, dass ich mir über den Zusammenhang von primitiv rekursiven Funktionen und partiell rekursiven Funktionen nicht so ganz klar bin!
LG, und nochmal vielen vielen Dank für die Hilfe! Meine Fragen scheinen irgendwie völlig idiotisch zu sein, aber leider kenn ich hier gerade niemanden, der mir das erklären könnte. Ich steh einfach auf dem Schlauch...
Ada
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:27 Mo 05.07.2010 | | Autor: | felixf |
Moin,
> Zeigen Sie, dass die folgenden Funktionen partiell rekursiv
> ist.
>
> g : N → N mit
> g(m) = [mm]\begin{cases} log_2m, & \mbox{für }\wurzel{m} \in N \mbox{ \inN} \\ undefiniert, & \mbox{sonst } \end{cases}[/mm]
das [mm] $\sqrt{m}$ [/mm] soll wohl auch ein [mm] $\log_2 [/mm] m$ sein ;)
>
> Hallo!
>
> Diese Teilaufgabe müsste sich ja dann analog zu
> Aufgabenteil 1 lösen lassen, indem ich die Funktion f(m)=
> [mm]|2^n-m|[/mm] betrachte, beweise, dass diese primitiv rekursiv
> ist, was wir in der Vorlesung bereits sowohl für
> Additions- als auch für Exponentialfunktionen bewiesen
> haben. Und daraus kann ich dann folgern , dass µf(m)=
> g(m), d.h. g(m) ist partiell rekursiv.
Genau.
> Mein Problem ist, dass ich mir über den Zusammenhang von
> primitiv rekursiven Funktionen und partiell rekursiven
> Funktionen nicht so ganz klar bin!
Nun, jede primitiv rekursive Funktion ist auch partiell rekursiv.
Schau dir mal die Definitionen an: hier und hier. Da siehst du, dass die Menge der partiell rekursiven Funktionen (potentiell) groesser ist als die Menge der primitiv rekursiven, da du eine Operation mehr zur Hand hast -- naemlich das [mm] $\mu$. [/mm] Alle anderen Operationen und Grundfunktionen sind gleich. Also ist jede primitiv rekursive Funktion auch partiell rekursiv.
LG Felix
|
|
|
|
