Primitive Rekursion

Primitive Rekursion

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-rekursiven Funktionen sind im intuitiven Sinn berechenbar. Sie schöpfen aber nicht alle intuitiv berechenbaren Funktionen aus, Beispiele dafür sind die Ackermannfunktion und die Sudanfunktion, welche beide berechenbar aber nicht primitiv-rekursiv sind. Eine vollständige Erfassung des Berechenbarkeitsbegriffs gelingt erst durch die µ-rekursiven 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-rekursiven Funktionen und der LOOP-berechenbaren (vgl. LOOP-Programm) Funktionen sind äquivalent.

Inhaltsverzeichnis

Definition

  1. Für ein beliebiges k\in \mathbb{N} ist die k-stellige Nullfunktion 0^k: \mathbb{N}^k \to \mathbb{N} definiert durch 0^k \left( n_1,\dots, n_k \right) := 0.
  2. Für ein beliebiges k\in \mathbb{N} und ein beliebiges 1 \le i \le k ist die k-stellige Projektion auf den i-ten Parameter \pi^k_i: \mathbb{N}^k \to \mathbb{N} definiert durch \pi_i^k \left( n_1,\dots, n_k \right) := n_i.
  3. Die Nachfolgerfunktion \nu: \mathbb{N} \to \mathbb{N} ist definiert durch \nu \left( n \right) := n + 1.
  4. Für beliebige k,m \in \mathbb{N} ist die Komposition einer Funktion g: \mathbb{N}^m \to \mathbb{N} mit m Funktionen h_1,\dots, h_m: \mathbb{N}^k \to \mathbb{N} definiert als die Funktion C[g,h_1,\dots,h_m]: \mathbb{N}^k \to \mathbb{N} mit C[g,h_1,\dots,h_m]\left( n_1,\dots, n_k \right) := g \left( h_1 \left( n_1,\dots, n_k \right),\dots, h_m \left( n_1,\dots, n_k \right) \right).
  5. Für ein beliebiges k \in \mathbb{N} \setminus \{0\} ist die primitive Rekursion zweier Funktionen g: \mathbb{N}^{k-1} \to \mathbb{N} und h: \mathbb{N}^{k+1} \to \mathbb{N} definiert als die Funktion R[g,h]:\mathbb{N}^k \to \mathbb{N} mit
R[g,h]\left( n_1, n_2,\dots, n_k \right) := \begin{cases}g \left( n_2,\dots, n_k \right), & \mbox{falls } n_1=0\\h \left( R[g,h] \left( n_1 - 1, n_2,\dots, n_k \right), n_1 - 1, n_2,\dots, n_k \right), & \mbox{sonst.}\end{cases}

Die Menge Pr der primitiv-rekursiven Funktionen ist dann definiert als die kleinste Menge, die alle Nullfunktionen, alle Projektionen und die Nachfolgerfunktion enthält, und die unter Komposition und primitiver Rekursion abgeschlossen ist. Alltäglicher ausgedrückt heißt das: Eine Funktion ist genau dann primitiv-rekursiv, wenn man sie als Ausdruck mit den genannten Mitteln hinschreiben kann. Bereits als primitiv-rekursiv nachgewiesene Funktionen dürfen in dem Ausdruck vorkommen, denn sie können ja durch Einsetzen ihres Ausdrucks eliminiert werden.

Jede k-stellige primitiv-rekursive Funktion ist insbesondere immer auf ganz \mathbb{N}^k definiert. Funktionen mit kleinerem Definitionsbereich müssen erst geeignet auf ganz \mathbb{N}^k fortgesetzt werden, damit man primitiv-rekursive Funktionen erhält.

Beispiele

Addition

Die Addition +: \mathbb{N}^2 \to \mathbb{N} ist rekursiv definiert durch

m+n = \begin{cases}n, & \mbox{falls } m=0,\\ ((m-1)+n)+1, & \mbox{sonst}\end{cases}

für alle m,n\in \mathbb{N}. Es gilt also + = R[\pi^1_1,C[\nu,\pi^3_1]], die Addition ist damit primitiv-rekursiv.

Multiplikation

Die Multiplikation *: \mathbb{N}^2 \to \mathbb{N} ist rekursiv über die Addition definiert:

m*n = \begin{cases}0, & \mbox{falls } m=0,\\ (m-1)*n+n, & \mbox{sonst}\end{cases}

für alle m,n\in \mathbb{N}. Die Multiplikation ist primitiv-rekursiv, denn es gilt * = R[0^1,C[+,\pi^3_1,\pi^3_3]].

Potenz

Die Potenz pot: \mathbb{N}^2 \to \mathbb{N} mit der Bedeutung pot(m,n) = mn ist rekursiv über die Multiplikation definiert:

pot(m,n) = \begin{cases}1, & \mbox{falls } n=0,\\ pot(m,n-1)*m, & \mbox{sonst}\end{cases}

für alle m,n\in \mathbb{N}. Die Potenz ist primitiv-rekursiv, denn es gilt pot = C[R[C[\nu,0^1],C[*,\pi^3_1,\pi^3_3]],\pi^2_2,\pi^2_1]. Der Kontext C[\_,\pi^2_2,\pi^2_1] hat hierbei den Zweck, die beiden Parameter m und n miteinander zu vertauschen.

Vorgängerfunktion

Die Vorgängerfunktion ist nicht an der Stelle 0 definiert. Sie ist also nicht primitiv-rekursiv. Durch Fortsetzung an der Stelle 0 zum Beispiel mit dem Wert 0 kann man jedoch eine primitiv-rekursive Funktion daraus machen.

Die modifizierte Vorgängerfunktion p: \mathbb{N} \to \mathbb{N}, definiert durch

p(n):=\begin{cases}0, & \mbox{falls } n = 0,\\ n-1, & \mbox{sonst}\end{cases}

für alle n\in \mathbb{N} ist primitiv-rekursiv, denn es gilt p = R[0^0,\pi^2_2].

Subtraktion

Auch die Subtraktion ist nicht auf allen Paaren natürlicher Zahlen definiert. Man setzt also die Subtraktion durch Auffüllen mit Nullen fort auf ganz \mathbb{N}^2. Diese totale Subtraktion sub: \mathbb{N}^2 \to \mathbb{N} kann rekursiv charakterisiert werden durch

sub(m,n) = \begin{cases}m, & \mbox{falls } n=0,\\ p(sub(m,n-1)), & \mbox{sonst}\end{cases}

für alle m,n\in \mathbb{N}. Für die totale Subtraktion gilt sub = C[R[\pi^1_1,C[p,\pi^3_1]],\pi^2_2,\pi^2_1]; sie ist also primitiv-rekursiv.

Weitere Beispiele

  • Die zweistelligen Funktionen max und min 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, Akademischer Verlag, Heidelberg/Berlin 1996. 
  • A. Oberschelp: Rekusionstheorie. BI-Wissenschaftlicher-Verlag, Mannheim/Leipzig/Wien/Zürich 1993. 

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Rekursion — in einem Bildschirm Aufnahmeprogramm. Als Rekursion (lat. recurrere „zurücklaufen“) bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich selbst zu definieren (rekursive Definition). Wenn man mehrere Funktionen… …   Deutsch Wikipedia

  • μ-Rekursion — Die Klasse Pr der μ rekursiven Funktionen oder partiell rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. Sie beschreibt die Menge aller Funktionen, die im intuitiven Sinn… …   Deutsch Wikipedia

  • My-Rekursion — Die Klasse Pr der μ rekursiven Funktionen oder partiell rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. Sie beschreibt die Menge aller Funktionen, die im intuitiven Sinn… …   Deutsch Wikipedia

  • Μ-Rekursion — Die Klasse Pr der μ rekursiven Funktionen oder partiell rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. Sie beschreibt die Menge aller Funktionen, die im intuitiven Sinn… …   Deutsch Wikipedia

  • Rekursionsanfang — Dieser Artikel erläutert die Technik der rekursiven Definition; zum Begriff rekursive Menge siehe entscheidbar. Als Rekursion (lat. recurrere „zurücklaufen“) bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich …   Deutsch Wikipedia

  • Rekursionsformel — Dieser Artikel erläutert die Technik der rekursiven Definition; zum Begriff rekursive Menge siehe entscheidbar. Als Rekursion (lat. recurrere „zurücklaufen“) bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich …   Deutsch Wikipedia

  • Rekursionsschritt — Dieser Artikel erläutert die Technik der rekursiven Definition; zum Begriff rekursive Menge siehe entscheidbar. Als Rekursion (lat. recurrere „zurücklaufen“) bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich …   Deutsch Wikipedia

  • Rekursionstiefe — Dieser Artikel erläutert die Technik der rekursiven Definition; zum Begriff rekursive Menge siehe entscheidbar. Als Rekursion (lat. recurrere „zurücklaufen“) bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich …   Deutsch Wikipedia

  • Rekursiv — Dieser Artikel erläutert die Technik der rekursiven Definition; zum Begriff rekursive Menge siehe entscheidbar. Als Rekursion (lat. recurrere „zurücklaufen“) bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich …   Deutsch Wikipedia

  • Rekursive Endlosschleife — Dieser Artikel erläutert die Technik der rekursiven Definition; zum Begriff rekursive Menge siehe entscheidbar. Als Rekursion (lat. recurrere „zurücklaufen“) bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”