Μ-Rekursion

Der korrekte Titel dieses Artikels lautet „µ-Rekursion“. Leider ist dieser Titel in der Wikipedia aufgrund technischer Einschränkungen nicht möglich. Μ-Rekursion


μ-rekursive Funktionen spielen in der theoretischen Informatik eine Rolle, insbesondere in Zusammenhang mit Berechenbarkeit. Sie stellt eine Erweiterung der primitiv-rekursiven Funktionen dar. Im Gegensatz zu den primitiv-rekursiven Funktionen können mit μ-rekursiven Funktionen insbesondere auch Funktionen dargestellt werden, die nicht total, sondern partiell sind. Daher werden die μ-rekursiven Funktionen oft auch partiell-rekursive Funktionen genannt. Es gibt in der Klasse der μ-rekursiven Funktionen aber auch Funktionen, die total und nicht primitiv-rekursiv sind. Ein berühmtes Beispiel dafür ist die Ackermann-Funktion.

Eigenschaften

Die Klasse R der μ-rekursiven Funktionen (von \mathbb{N}^k \rightarrow \mathbb{N}) umfasst:

  1. alle konstanten Funktionen: f_c^k \left( n_1, ..., n_k \right) := c, c \in \mathbb{N}
  2. alle Projektionen: \pi_i^k \left( n_1, ..., n_k \right) := n_i, 1 \le i \le k
  3. die Nachfolgefunktion: \nu \left( n \right) := n + 1

und ist abgeschlossen gegenüber:

  1. der 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. Primitiver Rekursion: f \left( 0, n_2, ..., n_k \right) := g \left( n_2, ..., n_k \right), 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
  3. Anwendung des μ-Operators

Definition des μ-Operators

Für eine Funktion f:\mathbb{N}^{k+1} \rightarrow \mathbb{N} ist die Funktion \mu f : \mathbb{N}^k \rightarrow \mathbb{N} definiert durch:

\mu f(x) = \begin{cases} \min \{ n \geq 0 | f(n,x) = 0 \mbox{ und } f(m,x) \mbox{ ist definiert } \forall m < n \} & \mbox{falls das Minimum existiert} \\ \mbox{undefiniert} & \mbox{sonst.}\\ \end{cases}

μ nennt man μ-Operator. Jede μ-rekursive Funktion entspricht einer WHILE-Schleife (vgl. WHILE-Programm) und umgekehrt.

μ-Rekursion

See also: Μ-Rekursion, Ackermann-Funktion, Berechenbarkeit, Partielle Funktion, Primitiv-rekursive Funktion, Theoretische Informatik, Totale Funktion, WHILE-Programm