μ-Rekursion

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die Klasse Pr der μ-rekursiven Funktionen oder partiell-rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle (µ für griech. μικρότατος = das kleinste). Nach der Church-Turing-These beschreibt sie die Menge aller Funktionen, die im intuitiven Sinn berechenbar sind. Eine wichtige echte Teilmenge der μ-rekursiven Funktionen sind die primitiv-rekursiven Funktionen.

Die Klasse der μ-rekursiven Funktionen stimmt überein mit der Klasse der Turing-berechenbaren Funktionen sowie weiteren gleich mächtigen Berechenbarkeitsmodellen, wie dem Lambda-Kalkül, Registermaschinen und WHILE-Programmen.

Die primitiv-rekursiven Funktionen sind aus einfachen Grundfunktionen (konstante 0-Funktion, Projektionen auf ein Argument und Nachfolgerfunktion) durch Komposition und primitive Rekursion aufgebaut. Dadurch erhält man immer totale Funktionen, also Funktionen im eigentlichen Sinn. Die μ-rekursiven Funktionen sind demgegenüber partielle Funktionen, die aus denselben Konstrukten und zusätzlich durch die Anwendung des μ-Operators gebildet werden können. Durch die Anwendung des μ-Operators wird Partialität eingeführt. Jedoch ist nicht jede μ-rekursive Funktion nicht-total. Beispielsweise sind alle primitiv-rekursiven Funktionen auch μ-rekursiv. Ein Beispiel für eine nicht primitiv-rekursive, totale, μ-rekursive Funktion ist die Ackermannfunktion.

Definition des μ-Operators[Bearbeiten]

Für eine partielle Funktion f:\mathbb{N}^{k+1} \to \mathbb{N} und natürliche Zahlen x_1;\dots;x_k \in \N sei die Menge

M(f,x_1,\dots,x_k) = \{n \in \N | f(x_1,\dots,x_k,n) = 0\ \and\ \forall 0 \leq m \leq n \colon f(x_1,\dots,x_k,m) \downarrow \}

festgehalten, also die Gesamtheit aller n derart, dass f an der Stelle (x_1,\dots,x_k,n) identisch 0 verschwindet und zusätzlich für alle Punkte (x_1,\dots,x_k,m) mit m \leq n definiert ist.

Zu beachten ist dabei, dass M(f,x_1,\dots,x_k) als Menge natürlicher Zahlen genau dann ein Minimum besitzt, wenn sie nicht leer ist. (vgl. Wohlordnung)


Durch Anwendung des \mu-Operators auf f entstehe nun die partielle Funktion \mu f \colon \N^k \to \N definiert durch:

\mu f(x_1, \dots, x_k) = \begin{cases} \min M(f,x_1,\dots,x_k) & \mbox{falls } M(f,x_1,\dots,x_k) \not= \emptyset \\ \mbox{undefiniert} & \mbox{sonst}\\ \end{cases}

Insbesondere bildet der Operator \mu also eine (k+1)-stellige partielle Funktion auf eine k-stellige partielle Funktion ab.


Für berechenbares f kann das Programm zur Berechnung von \mu f verstanden werden als eine While-Schleife, die nach oben zählt, und die deswegen nicht terminieren muss:

Parameter: x_1, ..., x_k.
Setze n auf 0;
Solange f(x_1,\dots,x_k,n) \not= 0 erhöhe n um 1;
Ergebnis: n.

Definition der μ-rekursiven Funktionen[Bearbeiten]

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

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

Die μ-rekursiven Funktionen erhält man als Abschluss der Grundfunktionen bezüglich der drei folgenden Operationen:

  1. Die Komposition: f \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), falls g, h_1,\dots, h_m \in Pr
  2. Die Primitive Rekursion: f \left( 0, n_2,\dots, n_k \right) := g \left( n_2,\dots, n_k \right) und f \left( n_1 + 1, n_2,\dots, n_k \right) := h \left( f \left( n_1,\dots, n_k \right), n_1,\dots, n_k \right), falls h, g \in Pr
  3. Der μ-Operator.

Äquivalenz der μ-rekursiven Funktionen mit der Turingmaschine[Bearbeiten]

Es lässt sich beweisen, dass eine Turingmaschine (TM) durch μ-rekursive Funktionen simuliert werden kann. Es lässt sich auch beweisen, dass die Menge der μ-rekursiven Funktionen genau der Menge der Turing-berechenbaren Funktionen entspricht.

Beweis-Skizze für die Simulation der TM mit μ-rekursiven Funktionen

Man kann zeigen, dass sich die Konfiguration einer TM durch drei Zahlen a, b, c darstellen lässt. Genau so kann eine Funktion h(a,b,c)=y (eine bijektive Abbildung \mathbb{N}^3 \to \mathbb{N}) definiert werden, die eine geeignete Kodierung der TM ist.

Nehmen wir also eine primitiv-rekursive Funktion

f(n,x)= y,

die eine geeignete Kodierung der TM liefert für die Eingabe x nach n Berechnungsschritten,

und eine zweite primitiv-rekursive Funktion

g(y)=0 \lor g(y)=1,

die für eine Kodierung y als Ergebnis 0 liefert, falls y einen Endzustand der TM repräsentiert, und ansonsten 1.

Dann ergibt

\mathrm{Anzahl}(x)=\mu(g(f(n,x)))

die Anzahl der Schritte, die eine TM zur Berechnung bis zum Ende benötigt. Also bekommen wir mit

\mathrm{Berechnung}(x)=f(\mathrm{Anzahl}(x), x)

die Berechnung der TM in einem Endzustand bei der Eingabe x.

Bemerkung[Bearbeiten]

  • Die Berechenbarkeit einer μ-rekursiven Funktion bezieht sich auf Werte aus ihrem Definitionsbereich. Es existiert kein allgemeines Verfahren, das alle Werte liefert, die nicht zum Definitionsbereich einer μ-rekursiven Funktion gehören.
  • Der μ-Operator realisiert einen Suchprozess, der genau dann abbricht, wenn der gesuchte Wert existiert.

Beispiele[Bearbeiten]

Literatur[Bearbeiten]