Die Mathe-Redaktion - 24.08.2019 06:38 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Sept.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 323 Gäste und 3 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von mire2 StrgAltEntf
Mathematik » Logik, Mengen & Beweistechnik » Schema der primitiven Rekursion: Warum dreistellig?
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Schema der primitiven Rekursion: Warum dreistellig?
metabole
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 15.08.2016
Mitteilungen: 40
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2017-07-07


Hallo,

ich habe Anfängerprobleme mit den primitiv-rekursiven Funktionen.

Warum ist die h-Funktion im folgenden 3-stellig...

Sind <math>g: \mathbb{N}^{n-1} \to \mathbb{N}</math> und <math>h: \mathbb{N}^{n+1} \to \mathbb{N}</math> primitiv-rekursiv, dann ist auch <math>f: \mathbb{N}^{n} \to \mathbb{N}</math> primitiv rekursiv.

<math>f (0, x_2, \ldots, x_n) = g (x_1, \ldots, x_n) \,</math>
<math>f (k+1, x_2, \ldots, x_n) = h (k, f (k, x_2, \ldots, x_k), x_2, \ldots, x_n) \,.</math>

Wenn man nun aber als Beispiel die rekursive Definition der Multiplikation heranzieht:


<math>
mult(m, n) =
\begin{cases}
mult(m, n) = n\\
mult(m, n+1) = add(mult(m, n),n)\\
\end{cases}
</math>

... dann ist ...

<math>add(mult(m, n),n)</math>

... doch nur 2-stellig ?

Vielen Dank!



  Profil  Quote  Link auf diesen Beitrag Link
dromedar
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 26.10.2013
Mitteilungen: 5123
Aus: München
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2017-07-07


Hallo metabole,

für die Funktion <math>f(x_1,x_2)=x_1\cdot x_2</math> ist:

    <math>\displaystyle f(0,x_2)=0</math>

    <math>\displaystyle f(k+1,x_2)=f(k,x_2)+x_2</math>  .

Daraus lässt sich ablesen:

    <math>\displaystyle g(x_2)=0</math>

    <math>\displaystyle h(x_1,y,x_2)=y+x_2</math>

Hier liegt also ein Spezialfall vor:
* Die Funktion <math>g</math> hängt von ihrem Argument nicht ab, sondern ist konstant.
* Die Funktion <math>h</math> hängt von einem ihrer drei Argumente (nämlich <math>x_1</math>) nicht ab.

Aber dass ein Spezialfall nicht alle Möglichkeiten eines Formalismus ausschöpft, ist ja nicht verwunderlich.

Grüße,
dromedar



  Profil  Quote  Link auf diesen Beitrag Link
metabole
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 15.08.2016
Mitteilungen: 40
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2017-07-07


Hallo dromedar,

danke für Deine Antwort.

Kannst Du mir denn ein Beispiel für eine (einigermaßen triviale hoffentlich) Funktion geben, welche den "Formalismus ausschöpft" ?

Ich bedanke!

metabole



  Profil  Quote  Link auf diesen Beitrag Link
dromedar
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 26.10.2013
Mitteilungen: 5123
Aus: München
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2017-07-07


Ein Beispiel, in dem alle drei Argumente von <math>h</math> gebraucht werden, liefert das Pochhammer-Symbol <math>f(k,x)=(x)_k</math>. Hierfür ist

    <math>\displaystyle g(x_2)=1</math>  ,    <math>\displaystyle h(x_1,y,x_2)=y\cdot(x_2-x_1)</math>  .



  Profil  Quote  Link auf diesen Beitrag Link
metabole
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 15.08.2016
Mitteilungen: 40
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2019-01-17


2017-07-07 13:35 - dromedar in Beitrag No. 1 schreibt:
Hallo metabole,

für die Funktion <math>f(x_1,x_2)=x_1\cdot x_2</math> ist:

    <math>\displaystyle f(0,x_2)=0</math>

    <math>\displaystyle f(k+1,x_2)=f(k,x_2)+x_2</math>  .

Daraus lässt sich ablesen:

    <math>\displaystyle g(x_2)=0</math>

    <math>\displaystyle h(x_1,y,x_2)=y+x_2</math>

Hier liegt also ein Spezialfall vor:
* Die Funktion <math>g</math> hängt von ihrem Argument nicht ab, sondern ist konstant.
* Die Funktion <math>h</math> hängt von einem ihrer drei Argumente (nämlich <math>x_1</math>) nicht ab.

Aber dass ein Spezialfall nicht alle Möglichkeiten eines Formalismus ausschöpft, ist ja nicht verwunderlich.

Grüße,
dromedar
Welches ist denn Argument x1 bei h? k? oder f(k, x_1, ..., x_k)

Viele Grüße



  Profil  Quote  Link auf diesen Beitrag Link
metabole
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 15.08.2016
Mitteilungen: 40
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2019-01-18


Das Schema der primitiven Rekursion gibt es auch noch in der Form

<math>f (0,x_2,\ldots,x_n) = g(x_1,\ldots,x_n) \,</math>
<math>f (m+1, x_1,\ldots,x_n) = h(f(m, x_2, \ldots, x_k),m, x_2,\ldots,x_n) \,.</math>

Hier werden die Argumente m und <math>x_1,...,x2</math> der rekursiven Funktion <math>f</math> noch offensichtlicher am Ende des Funktionsaufrufs von <math>h</math> wiederholt... Welchen Sinn macht das?



  Profil  Quote  Link auf diesen Beitrag Link
metabole
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 15.08.2016
Mitteilungen: 40
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2019-01-19


Wenn ich so einen Restbestand an Argumenten habe, die eigentlich nicht gebraucht werden, brauche ich dann nicht die Projektionsfunktion?



  Profil  Quote  Link auf diesen Beitrag Link
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 584
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-01-19


2019-01-18 13:51 - metabole in Beitrag No. 5 schreibt:
Hier werden die Argumente m und <math>x_1,...,x2</math> der rekursiven Funktion <math>f</math> noch offensichtlicher am Ende des Funktionsaufrufs von <math>h</math> wiederholt... Welchen Sinn macht das?

$h$ kann von diesen Argumenten abhängen. Ein Beispiel für so ein $h$ hat doch oben vor mehr als einem Jahr schon dromedar angegeben:

2017-07-07 22:08 - dromedar in Beitrag No. 3 schreibt:
    <math>\displaystyle g(x_2)=1</math>  ,    <math>\displaystyle h(x_1,y,x_2)=y\cdot(x_2-x_1)</math>  .

2019-01-19 12:48 - metabole in Beitrag No. 6 schreibt:
Wenn ich so einen Restbestand an Argumenten habe, die eigentlich nicht gebraucht werden, brauche ich dann nicht die Projektionsfunktion?

Sie werden ja gebraucht. Und selbst wenn sie in einem Spezialfall nicht alle gebraucht werden (wie in deinem Beispiel im Startbeitrag), ist das doch auch kein Problem. Was willst du mit einer Projektionsfunktion?



  Profil  Quote  Link auf diesen Beitrag Link
metabole
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 15.08.2016
Mitteilungen: 40
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2019-01-19


Was ich mit der Projektionsfunktion möchte? Ich weiss nicht, sags mir :) Ich dachte für so einen Fall wäre die da: Wenn die Stelligkeit nicht ganz passt.

LG metabole



  Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1576
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-01-19


Die Projektionsfunktionen braucht man, um Argumente auszuwählen, um sie zum Beispiel an andere Funktionen weiterzureichen.
Ich bezeichne mit $f \bullet (g_1,\dots,g_n)\colon \IN^k \to \IN$ mal die Komposition von $f\colon \IN^n \to \IN$ mit den $g_i\colon \IN^k \to \IN$, definiert durch $$(f \bullet (g_1,...,g_n))(\vec x) := f(g_1(\vec x),\dots,g_n(\vec x))$$ für alle $\vec x \in \IN^k$. (Im Fall $n=1$ kann man statt $f\bullet(g_1)$ auch wie üblich $f\circ g_1$ schreiben.)
Ein paar Beispiele: Es seien $f\colon \IN^2 \to \IN$ und $f_2\colon \IN \to \IN$ primitiv rekursiv.
$h\colon \IN \to \IN, h(x) := f(x,x)$ ist dann primitiv rekursiv, weil $h=f\bullet(\pi_1^1,\pi_1^1)$.
$h\colon \IN^3 \to \IN, h(x,y,z) := f(x,f_2(z))$ ist primitiv rekursiv, weil $h=f\bullet(\pi_1^3, f_2 \bullet(\pi_3^3))$
$h\colon \IN^2 \to \IN, h(x,y) := f(y,x)$ ist primitiv rekursiv, weil $h = f\bullet(\pi_2^2, \pi_1^2)$.
Dass $h\colon \IN^2 \to \IN, h(x,y) := f(x,y)$ primitiv rekursiv ist, kann man damit begründen, dass $h=f$, aber man kann auch im Schema bleiben und es damit begründen, dass $h=f\bullet(\pi_1^2,\pi_2^2)$ ist.



  Profil  Quote  Link auf diesen Beitrag Link
metabole hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]