Das Kefk Network Wiki befindet sich im Testbetrieb.

Primitiv-rekursive Funktion

Aus Kefk.

Wechseln zu: Navigation, Suche

Primitiv-rekursive Funktionen sind totale Funktionen, die aus einfachen Grundfunktionen (konstante 0-Funktion, Projektionen auf ein Argument und Nachfolgefunktion) durch Komposition und (primitive) Rekursion gebildet werden können. Der Begriff primitiv-rekursive Funktion wurde von der ungarischen Mathematikerin Rózsa Péter geprägt. Primitiv-rekursive Funktionen spielen in der Rekursionstheorie, einem Teilgebiet der Theoretischen Informatik, eine Rolle. Sie treten im Zusammenhang mit der Explikation des Berechenbarkeitsbegriffs auf.

Alle primitiv-rekursive Funktionen sind im intuitiven Sinn berechenbar. Sie schöpfen aber nicht alle intuitiv berechenbare Funktionen aus, Beispiele dafür sind die Ackermannfunktion und die Sudanfunktion, welche beide berechenbar aber nicht primitiv-rekursiv sind. Eine vollständige Erfassúng des Berechenbarkeitsbegriffs gelingt erst durch die µ-rekursive Funktionen.

Für primitiv-rekursive Funktionen ist es möglich, ein Komplexitätsmaß zu definieren, d. h. es kann die Dauer der Berechnung eines ihrer Funktionswerte vorab ermittelt werden.

Die Klasse der primitiv-rekursive Funktion und der LOOP-berechenbaren (vgl. LOOP-Programm) Funktionen sind äquivalent.


Inhaltsverzeichnis

Definition

Die Klasse Pr der primitiv-rekursiven Funktionen (von \mathbb{N}^k \rightarrow \mathbb{N}) umfasst die folgenden Grundfunktionen:

  1. konstante 0-Funktion: f^k \left( n_1, ..., n_k \right) := 0
  2. Projektion auf ein Argument: \pi_i^k \left( n_1, ..., n_k \right) := n_i, 1 \le i \le k
  3. Nachfolgefunktion: \nu \left( n \right) := n + 1 (auch Sukzessorfunktion genannt)

Die primitiv-rekursiven Funktionen erhält man als Abschluss der Grundfunktionen bezügliche der beiden folgenden Operationen:

  1. Die Komposition: f \left( n_1, ..., n_k \right) := g \left( h_1 \left( n_1, ..., n_k \right), ..., h_m \left( n_1, ..., n_k \right) \right), falls g, h_1, ..., h_m \in Pr
  2. Die Primitive Rekursion: f \left( 0, n_2, ..., n_k \right) := g \left( n_2, ..., n_k \right) und f \left( n_1 + 1, n_2, ..., n_k \right) := h \left( f \left( n_1, ..., n_k \right), n_1, ..., n_k \right), falls h, g \in Pr

Beispiele

Vorgängerfunktion

Die modifizierte Vorgängerfunktion p(x):=x-1\; für 1\leq x\; und p(0):=0\; ergibt sich durch primitive Rekursion. Als Funktion g verwendet man die Nullfunktion und als Funktion h die Projektion. Es ergibt sich dadurch:

g(0)=0\;

p(n+1)=h(p(n),n)=\pi_2^2(p(n),n)=n

Addition

Die Addition \mbox{add} \left(a,b \right)=a+b natürlichen Zahlen lässt sich wie folgt definieren:

\mbox{add}(0,b):=\pi_1^1(b)=b (Projektion)

\mbox{add}(n+1,b):=\nu \left(\mbox{add}(n,b) \right) (Primitive Rekursion)

Um aus der Addition eine Subtraktion zu machen ersetzt man die Nachfolgerfunktion ν durch die Vorgängerfunktion p.

Multiplikation

Zur Definition der Multiplikation \mbox{mult}(a,b)=a\cdot b dürfen wir die Addition schon verwenden, da diese ja, wie gerade gezeigt, primitiv-rekursiv ist:

\mbox{mult}(0,b):=f_0^1(b)=0 (konstante Funktion)

\mbox{mult}(n+1,b):=\mbox{add}\left(b,\mbox{mult}(n,b)\right)=\mbox{mult}(n,b)+b (Primitive Rekursion)

Potenzieren

Zur Definition des Potenzierens pot(a,b) = ab dürfen wir die Addition und Multiplikation schon verwenden, da diese ja, wie gerade gezeigt, primitiv-rekursiv sind:

\mbox{pot}(a,0):= v(0)=1\; (konstante Funktion)

\mbox{pot}(a,v(b)):= \mbox{mult}\left(\mbox{pot}(a,b),a \right)= (Primitive Rekursion)

Weitere Beispiele

  • Die Funktionen max\left(x,y\right), min\left(x,y\right) und \left|x\right| sind primitiv rekursiv.
  • Die Folge der Primzahlen ist eine primitiv rekursive Funktion.
  • Die Funktion, die zu einer natürlichen Zahl n und einer Primzahl p die Anzahl der Primfaktoren von p in n ermittelt, ist primitiv rekursiv.
  • Es existieren primitiv rekursive Arithmetisierungen endlicher Folgen natürlicher Zahlen.
  • Die Ackermannfunktion und die Sudanfunktion sind nicht primitiv rekursiv aber µ-rekursiv.
  • Die Funktion Fleißiger Biber (busy beaver) ist nicht primitiv rekursiv und nicht µ-rekursiv.

Siehe auch:

Literatur

  • H.-D. Ebbinghaus, J. Flum, W. Thomas; Einführung in die mathematische Logik; Spektrum, Akad. Verl.; Heidelber, Berlin; 1996
  • A. Oberschelp; Rekusionstheorie; BI-Wiss.-Verl.; Mannheim, Leipzig, Wien, Zürich; 1993.

Weblinks

Wikipedia
 Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Primitiv-rekursive_Funktion, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.
Von „http://kefk.org/wiki/Primitiv-rekursive_Funktion“
Persönliche Werkzeuge