Wie Rekursion definieren?

16/01/2012 - 18:34 von carlox | Report spam
Hallo allerseits,
eine konkrete Rekursion kann man leicht notieren, wie z.B.
fak(n) = n * fak(n-1)
fak(1) = 1

Frage:
Wie kann man den _allgemeinen_ Fall (nicht nur natuerliche Zahlen)
einer rekursiven Funktion formal spezifizieren (definieren)?

mfg
Ernst
 

Lesen sie die antworten

#1 Hans CraueI
16/01/2012 - 20:54 | Warnen spam
Ernst Baumann schrieb

eine konkrete Rekursion kann man leicht notieren, wie z.B.
fak(n) = n * fak(n-1)
fak(1) = 1

Frage:
Wie kann man den _allgemeinen_ Fall (nicht nur natuerliche Zahlen)
einer rekursiven Funktion formal spezifizieren (definieren)?



Folgen lassen sich rekursiv definieren. Die Folgen muessen dabei
nicht nur, wie dein Beispiel der Fakultaet, Werte in den
natuerlichen Zahlen annehmen. Ganz einfach: X eine Menge, F eine
Abbildung von X nach X, dann gibt die Setzung x(n+1) = F(x(n)),
x(1) = x_0 fuer ein beliebiges x_0 aus X, eine auf der allgemeinen
Menge X rekursiv definierte Folge.

Insoweit es um die Definition von Folgen als `Funktionen auf den
natuerlichen Zahlen' geht, beruht die Moeglichkeit, derartige
Funktionen rekursiv zu definieren, auf der Peano-Eigenschaft der
natuerlichen Zahlen: Die Menge M aller natuerlichen Zahlen, fuer
die durch die Rekursion der Funktionswert definiert wird, hat die
Eigenschaften: 1 ist Element von M, und ist n Element von M, so
ist auch n+1 Element von M. Also enthaelt M die natuerlichen Zahlen.
Dies geht mit allgemeinen Mengen nicht. Durch eine derartige
Rekursion laesst sich nur dann eine Funktion defnieren, wenn die
Menge abzaehlbar ist.

Eine Moeglichkeit einer Verallgemeinerung erhaelt man ueber
Differentialgleichungen: Man hat eine Funktion F von R^n nach
R^n (oder, allgemeiner, von einem Hilbert- bzw. Banach-Raum in
sich selbst, oder auf einer Mannigfaltigkeit). Man sucht nun
Funktionen x von R nach R^n (bzw. dem Hilbert- bzw. Banach-Raum
oder der Mannigfaltigkeit), die
x' = F(x)
oder, etwas genauer,
x'(t) = F(x(t)) fuer alle (oder jedenfalls moeglichst
viele) reelle t
erfuellen, dabei steht x' fuer die Ableitung der Funktion x nach t.
Das ist eine (gewoehnliche) Differentialgleichung, kurz Dgl.
Dazu fordert man x(0) = x_0 und bekommt damit ein sogenanntes
Anfangswertproblem (AWP).

Anders als bei einer Rekursion, die durch eine beliebige Funktion
F von einer beliebigen Menge X nach X selbst gegeben wird, lassen
sich Dgl. nicht auf allgemeinen Mengen definieren. Man muss dafuer
sorgen, dass x' und F(x) Werte im gleichen Raum annehmen und
braucht dafuer eine Menge, die eine `differenzierbare Struktur'
hat. Auch wenn man dies alles hat, muss eine Dgl. x' = F(x) damit
noch lange keine Loesungen haben, und wenn doch, muessen die
keineswegs eindeutig sein, und wenn doch, muessen die keineswegs
fuer alle reellen oder auch nur alle nichtnegativen reellen t
existieren.
Von daher kann man unterschiedlicher Ansicht darueber sein, ob
Dgl. tatsaechlich als Verallgemeinerung rekursiv definierter
Folgen betrachtet werden koennen. Gemeinsame Untersuchung beider
Gebiete findet teilweise bei den "Dynamischen Systemen" statt.

Hans CraueI

Ähnliche fragen