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. Die primitive Rekursion lässt sich auf Richard Dedekinds 126. Theorem in Was sind und was sollen die Zahlen? (1888) zurückführen. Die primitiv rekursive Arithmetik geht auf Thoralf Skolem (1923) zurück.[1] 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 die der LOOP-berechenbaren (vgl. LOOP-Programm) Funktionen sind äquivalent.

Definition

Bearbeiten
  1. Für ein beliebiges   ist die k-stellige 0-Funktion   definiert durch  .
  2. Für ein beliebiges   und ein beliebiges   ist die k-stellige Projektion auf den i-ten Parameter   definiert durch  .
  3. Die Nachfolgerfunktion   ist definiert durch  .
  4. Für beliebige   ist die Komposition einer Funktion   mit m Funktionen   definiert als die Funktion   mit  .
  5. Für ein beliebiges   ist die primitive Rekursion zweier Funktionen   und   definiert als die Funktion   mit
 

Die Menge   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   definiert. Funktionen mit kleinerem Definitionsbereich müssen erst geeignet auf ganz   fortgesetzt werden, damit man primitiv-rekursive Funktionen erhält.

Beispiele

Bearbeiten

Addition

Bearbeiten

Die Addition   ist rekursiv definiert durch

 

für alle  . Es gilt also  , die Addition ist damit primitiv-rekursiv.

Multiplikation

Bearbeiten

Die Multiplikation   ist rekursiv über die Addition definiert:

 

für alle  . Die Multiplikation ist primitiv-rekursiv, denn es gilt  .

Die Potenz   mit der Bedeutung   ist rekursiv über die Multiplikation definiert:

 

für alle  . Die Potenz ist primitiv-rekursiv, denn es gilt  . Der Kontext   hat hierbei den Zweck, die beiden Parameter   und   miteinander zu vertauschen.

Vorgängerfunktion

Bearbeiten

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  , definiert durch

 

für alle   ist primitiv-rekursiv, denn es gilt  .

Subtraktion

Bearbeiten

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  . Diese totale Subtraktion   kann rekursiv charakterisiert werden durch

 

für alle  . Für die totale Subtraktion gilt  ; sie ist also primitiv-rekursiv. Man nennt diese modifizierte Differenz auch arithmetische Differenz.

Weitere Beispiele

Bearbeiten
  • Die zweistelligen Funktionen   und   sind primitiv rekursiv.
  • Die Folge der Primzahlen ist eine primitiv rekursive Funktion.
  • Die Funktion, die zu einer natürlichen Zahl   und einer Primzahl   die Anzahl der Primfaktoren von   in   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

Bearbeiten

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten
  1. Peter Schroeder-Heister, Mathematische Logik II (Gödelsche Unvollständigkeitssätze), Skript, S. 39