Die Mathe-Redaktion - 23.03.2019 16:23 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
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 490 Gäste und 33 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 » primitiv rekursive Funktionen - (definitorische) Voraussetzungen
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich primitiv rekursive Funktionen - (definitorische) Voraussetzungen
metabole
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 15.08.2016
Mitteilungen: 40
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-01-12


Hallo,

im Eintrag tzr rekursiven Definition steht erläuternd zu dem Beispiel in der Enzyklopädie herausgegeben von Jürgen Mittelstraß zum Eintrag "Definition, rekursive":

"... dabei wurden neben (A2) und (A1) noch die definitorischen Fakten verwendet, daß 1 der Nachfolger von 0 und 3 der Nachfolger von 2 ist."

Die r.F.en. scheinen also nicht ohne (definitorische) Voraussetzungen auszukommen.

Wenn man also die Axiome für die Addton so definiert:
add(m + 0) := m
add(m + n') := add(m + n)'

Kommt man bei der rekursiven Addition aus, ohne zur Nachfolge Funktion der Peano-Axiome weitere Voraussetzungen hinzuzunehmen? Ich versuche einige wenige Argumente, hoffentlich einigermaßen stringent, hervorzubringen. Ich hoffe, daß diese einigermaßen Sinn machen.

- Ausgangspunkt ist die 0 und die Anzahl der Symbole für die Nachfolgefunktion.

- Dann werden diese Symbole so lange verringert, bis man bei der Abbruchbedingung (n = 0) angekommen ist.

0 + m := m

- Dies setzt eine Vorgänger- bzw. Minusfunktion voraus.

- Diese liefert m als bereits vorausgesetzte Zahl zurück. m wird nicht noch einmal rekursiv errechnet. [m wird einfach vorausgesetzt]

- Wenn man sich bewußt macht, daß Zahlen der Peano-Arithmetik die Form wie
 
add(0''',0'''''') := (add(0''',0'''''))'

haben, muss ich ja schon beim Ergebnis anfangen, wenn ich auf 0 runter-"subtrahiere", oder nicht?

- Im endeffekt handelt es sich nicht um eine add-Funktion, sondern um eine "add-to-m"-Funktion. Ich kann die Argumente nicht vertauschen. Dann wird die Rekursion nur auf das eine Argument angewandt, das andere ("m") wird so wie es ist zurückgeliefert. [Keine beliebige Vertauschbarkeit der beiden Argumente]

- Eine Implementierung hingegen mit zusätzlicher Minus-Funktion ist einfach. Hier wird m einfach als Schleifenvariable benutzt.
c
int add(m, n)
{
        if (m == 0) {
                return n;
        } else {
                return {
                        succ(add(m-1, n));
        }
}



Viele Grüße,

metabole



  Profil  Quote  Link auf diesen Beitrag Link
metabole
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 15.08.2016
Mitteilungen: 40
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, vom Themenstarter, eingetragen 2019-01-12


Kann jemand vielleicht bitte eine Anwendung (ein Beispiel) der Addition nennen, die nur mit der Nachfolgefunktion auskommt?

Vielen Dank

metabole



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

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner}\)
Primitive Rekursion (etwas higher-order) sagt: Für alle Mengen $A$, Elemente $x_0 \in A$ und Funktionen $f\colon A \to A$ gibt es eine eindeutig bestimmte Funktion $h\colon \IN \to A$ mit $h(0) = x_0$ und für alle $n\in \IN$, $h(n') = f(h(n))$. Eine Vorgängeroperation braucht man nicht, wenn man eine Funktion durch primitive Rekursion definieren will. Die Analyse, ob eine natürliche Zahl 0 oder ein Nachfolger ist (und im letzteren Fall vor allem: wovon), wird einem schon abgenommen.
Fall Addition: Hier kann man statt $\mathsf{plus}\colon \IN\times \IN \to \IN$ die Curry-transformierte $\mathsf{plus'}\colon \IN \to \IN^\IN$ betrachten.
Es gibt nun (mindestens) zwei Möglichkeiten, Addition durch primitive Rekursion zu definieren.
1) Man definiert $\mathsf{plus'}(n)\colon \IN \to \IN$ für jedes $n$. Dazu braucht man jeweils ein Element $x_0\in \IN$ (dazu nimmt man $n$) und eine Funktion $f\colon \IN \to \IN$ (dazu nimmt man $f := (-)'$, bzw. $f(m) := m'$).
2) Man definiert $\mathsf{plus'}\colon \IN \to \IN^\IN$ durch primitive Rekursion. Dazu braucht man ein Element $x_0\in \IN^\IN$ (dazu nimmt man $\mathrm{id}_\IN$) und eine Funktion $f\colon \IN^\IN \to \IN^\IN$ (dazu nimmt man $g \mapsto (-)' \circ g$, bzw. $f(g)(m) := (g(m))'$, oder vielleicht auch $f(g)(m) := g(m')$).
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
metabole
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 15.08.2016
Mitteilungen: 40
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2019-01-13


wenn man eine Funktion durch primitive Rekursion definieren will. Die Analyse, ob eine natürliche Zahl 0 oder ein Nachfolger ist (und im letzteren Fall vor allem: wovon), wird einem schon abgenommen.
(was ist nochmal die Syntax für quote?)



Hallo, das ist interessant!


kannst Du mir das mit dem currying (auf diesen Fall bezogen) noch einmal erklären? Vielen Dank !



  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 909
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-01-13


2019-01-12 23:06 - tactac in Beitrag No. 2 schreibt:
Primitive Rekursion (etwas higher-order) sagt:

Hallo tactac,
was meinst du mit dem Begriff "Primitive Rekursion"?
Wo kommt er her?
Sind das primitiv rekursive Funktionen aus der Berechenbarkeitstheorie ?
Kannst du eine Quelle nennen ?

mfg
cx



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

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner}\)
2019-01-13 10:08 - carlox in Beitrag No. 4 schreibt:
2019-01-12 23:06 - tactac in Beitrag No. 2 schreibt:
Primitive Rekursion (etwas higher-order) sagt:

Hallo tactac,
was meinst du mit dem Begriff "Primitive Rekursion"?
Wo kommt er her?
Sind das primitiv rekursive Funktionen aus der Berechenbarkeitstheorie ?
Ich habe das Grundprinzip der primitiven Rekursion erklärt: Es wird eine Funktion iteriert. Die primitv rekursiven Funktionen aus der Berechenbarkeitstheorie erhält man durch eine Pseudoverallgemeinerung des angegebenen Schemas mit nachfolgender Spezialisierung.
Bei den primitivrekursiven Funktionen aus der Berechenbarkeitstheorie kann man das $A$ nicht frei wählen, sondern es ist immer $\IN$. Daher können wir von Currying keinen Gebrauch machen. Außerdem ist es bequem, aber nicht nötig, der Funktion, die iteriert wird, noch mitzuteilen, beim wievielten Schritt man ist. Das pseudoverallgemeinerte Schema ist dann:
Für beliebige Mengen $\Gamma$ und $A$ und Funktionen $v_0\colon \Gamma \to A$, $f\colon \Gamma\times \IN\times A \to A$ gibt es eine eindeutig bestimmte Funktion $h\colon \Gamma\times\IN \to A$ mit $h(\gamma,0) = v_0(\gamma)$ und $h(\gamma,n') = f(\gamma,n,h(\gamma,n))$.

Das Schema, das in der Definition primitiv rekursiver Funktionen benutzt wird, erhält man, indem man nun fordert, dass $\Gamma$ von der Form $\IN^k$ ist, $A=\IN$, und $v_0$ sowie $f$ primitiv rekursiv. Das $h$ das damit herauskommt, ist per Definition primitiv rekursiv.


Kannst du eine Quelle nennen ?
Wofür? Eine Variante, die nicht auf $\IN$ und $\IN^k$ einschränkt, definiert jedenfalls Dinge, die "primitiv rekursive Funktionale" heißen.
\(\endgroup\)


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

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner}\)
2019-01-13 09:20 - metabole in Beitrag No. 3 schreibt:
kannst Du mir das mit dem currying (auf diesen Fall bezogen) noch einmal erklären? Vielen Dank !
Statt $\mathsf{plus}\colon \IN\times \IN \to \IN$ definieren wir $\mathsf{plus'}\colon \IN \to \IN^\IN$, das die Eigenschaft haben soll, dass $\mathsf{plus'}(n)(m) = \mathsf{plus}(n,m)$. $\mathsf{plus}$ nimmt ein Paar natürlicher Zahlen entgegen und liefert eine natürliche Zahl, $\mathsf{plus'}$ dagegen nimmt nur eine natürliche Zahl und liefert eine Funktion $\IN \to \IN$. Mehr ist da nicht dran.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 909
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-01-15





Kannst du eine Quelle nennen ?
Wofür? Eine Variante, die nicht auf $\IN$ und $\IN^k$ einschränkt, definiert jedenfalls Dinge, die "primitiv rekursive Funktionale" heißen.


Kannst du eine Quelle nennen ?
Wofür? Eine Variante, die nicht auf $\IN$ und $\IN^k$ einschränkt, definiert jedenfalls Dinge, die "primitiv rekursive Funktionale" heißen.

Warum fragst du "Wofür" ?
Zum Nachlesen und weil Quellen die Basics wissenschaftlichen Arbeitens sind.

Mit verwunderten Grüssen
cx




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


2019-01-15 08:34 - carlox in Beitrag No. 7 schreibt:
Warum fragst du "Wofür" ?
Zum Nachlesen und weil Quellen die Basics wissenschaftlichen Arbeitens sind.

Mit verwunderten Grüssen
cx
Ich frage nach dem Gegenstand, nicht nach dem Grund.



  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 909
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-01-15



Ich frage nach dem Gegenstand, nicht nach dem Grund.
Ich will einfach wissen, wo noch - ausser der mir bekannten "Klasse der primitiv rekursiven Funktionen" (Paul, Komplexitätstheorie Teubner Verlag) dieser Begriff verwendet (evtl. aber verschieden) wird.

mfg
cx
 



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

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner}\)
2019-01-15 13:22 - carlox in Beitrag No. 9 schreibt:
Ich will einfach wissen, wo noch - ausser der mir bekannten "Klasse der primitiv rekursiven Funktionen" (Paul, Komplexitätstheorie Teubner Verlag) dieser Begriff verwendet (evtl. aber verschieden) wird.
Immer noch unklar. Primitive Rekursion ist nicht dasselbe wie die Klasse primitiv rekursiver Funktionen. Ich sprach von ersterem.
Aber hier trotzdem mal ein paar Links:
Siehe z.B: www.jucs.org/jucs_10_7/total_functional_programming oder en.wikipedia.org/wiki/Primitive_recursive_functional und darin referenziertes zwecks Fallenlassen der Einschränkung auf $\IN^k \to \IN$.
Dass die eigentliche Essenz Iteration ist, sieht man z.B. daran, wie NNOs in kartesisch abgeschlossenen Kategorien definiert werden.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
metabole
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 15.08.2016
Mitteilungen: 40
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2019-01-15


Kann ich denn die Argumente der add-Funktion vertauschen?

Bei add(m',n) = add(m + n)'

wird doch entweder m oder n definitorisch vorausgesetzt, oder nicht?



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


2019-01-15 15:12 - metabole in Beitrag No. 11 schreibt:
Kann ich denn die Argumente der add-Funktion vertauschen?

Bei add(m',n) = add(m + n)'

wird doch entweder m oder n definitorisch vorausgesetzt, oder nicht?
Es wird immer nur in einem Argument abgestiegen. Welches das ist, ist aber bis auf Technikalitäten egal, denn man kann ja der Funktion, die sich aus einer rekursiven Definition ergibt, eine Argumentvertauschung vorschalten.



  Profil  Quote  Link auf diesen Beitrag Link
metabole
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 15.08.2016
Mitteilungen: 40
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, vom Themenstarter, eingetragen 2019-01-15


Tactac, Deine Antworten sind eifach zu hoch für einen Anfänger wie mich  confused  smile

Ich denke den ersten Teil verstehe ich und die Konsequenz ist die von mir gemeinte: Sobald das Argument, auf das die Naxhfolgerdunktion angewendet wird, bei 0 ist, wird mir entweder m oder n wiedergegeben.

Den zweiten Teil von Deinem Posting verstehe ich wieder einmal nicht. Kurz, knapp, effizient. Wenig Erklärung für einen Anfänger. Soll sich bitte nicht undankbar oder nach Kritik anhören. Su bist halt scheinbar schon ein "alter Hase", für Dich sind das Trivialitäten.

Ich stehe vor Projektionsfunktion. Kompositions-Schema, Schema der primitiven Rekursion - und versuche einen Sinn da rein zu bringen. Vielleicht bin ich auch einfach zu blöd... ?!

Vielen Dank jedenfalls für Deine Beteiligung!



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

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner}\)
Nun, es kann sein, dass die Definition verlangt, dass z.B. immer nur im ersten Argument abgestiegen werden darf, d.h. dass eine rekursive Definition immer so aussehen muss:
$f(0,\vec x) := \phi$,
$f(n',\vec x) := \psi$,
wobei $f$ in $\phi$ nicht vorkommen darf und in $\psi$ nur als Teilterm der Form $f(n,\vec x)$.
Wenn nun die Aufgabe darin besteht, $\mathsf{pow}\colon \IN^2 \to \IN$ zu definieren mit $\mathsf{pow}(a,e) = a^e$, würde Abstieg im zweiten Argument besser gehen. Man kann dies dann so lösen, dass man eine Hilfsfunktion $\mathsf{wop}$ rekursiv definiert mit $\mathsf{wop}(e,a) = a^e$, zum Beispiel durch
$\mathsf{wop}(0,a) := 1$,
$\mathsf{wop}(n',a) := a\cdot \mathsf{wop}(n,a)$
und dann mittels Projektion und Komposition $\mathsf{pow}(a,e) := \mathsf{wop}(e,a)$.
\(\endgroup\)


  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]