Μ-Rekursion

Die Klasse Pr der μ-rekursiven Funktionen oder partiell-rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle (µ für griechisch μικρότατος ‚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

Für eine partielle Funktion $f : ℕ^{k + 1} \to ℕ$ und natürliche Zahlen $x_{1}; \dots; x_{k} \in ℕ$ sei die Menge

M (f, x_{1}, \dots, x_{k}) = {n \in ℕ ∣ f (x_{1}, \dots, x_{k}, n) = 0 \land \forall 0 \leq m \leq n : f (x_{1}, \dots, x_{k}, m) ↓}

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 $μ$ -Operators auf $f$ entstehe nun die partielle Funktion $μ f : ℕ^{k} \to ℕ$ , definiert durch:

μ f (x_{1}, \dots, x_{k}) = {\begin{matrix} min M (f, x_{1}, \dots, x_{k}), & falls M (f, x_{1}, \dots, x_{k}) \neq ∅︀ \\ undefiniert & sonst \end{matrix}

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

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

Parameter: $x_{1}, \dots, x_{k}$ .
Setze $n$ auf $0$ ;
Solange $f (x_{1}, \dots, x_{k}, n) \neq 0$ , erhöhe $n$ um $1$ ;
Ergebnis: $n$ .

Definition der μ-rekursiven Funktionen

Die Klasse $P r$ der μ-rekursiven Funktionen ( $ℕ^{k} \to ℕ$ ) umfasst die folgenden Grundfunktionen:

konstante 0-Funktion: $f^{k} (n_{1}, \dots, n_{k}) := 0$
Projektion auf ein Argument: $π_{i}^{k} (n_{1}, \dots, n_{k}) := n_{i}$ , $1 \leq i \leq k$
Nachfolgefunktion: $ν (n) := n + 1$

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

der Komposition: $f (n_{1}, \dots, n_{k}) := g (h_{1} (n_{1}, \dots, n_{k}), \dots, h_{m} (n_{1}, \dots, n_{k}))$ , falls $g, h_{1}, \dots, h_{m} \in P r$
der primitiven Rekursion: $f (0, n_{2}, \dots, n_{k}) := g (n_{2}, \dots, n_{k})$ und $f (n_{1} + 1, n_{2}, \dots, n_{k}) := h (f (n_{1}, \dots, n_{k}), n_{1}, \dots, n_{k})$ , falls $h, g \in P r$
des μ-Operators.

Äquivalenz der μ-rekursiven Funktionen mit der Turingmaschine

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 $ℕ^{3} \to ℕ$ ) 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

A n z a h l (x) = μ (g (f (n, x)))

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

B e r e c h n u n g (x) = f (A n z a h l (x), x)

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

Bemerkung

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

Alle primitiv-rekursiven Funktionen sind μ-rekursiv.
Die Ackermannfunktion und die Sudanfunktion sind totale μ-rekursive Funktionen, die nicht primitiv-rekursiv sind.
Die Funktion Fleißiger Biber (busy beaver) ist nicht μ-rekursiv.
Die Folge der Ziffern der Halte-Wahrscheinlichkeit (Chaitinsche Konstante $Ω$ ) ist nicht μ-rekursiv. Die Halte-Wahrscheinlichkeit ist definiert durch

Ω := \sum_{p} 2^{- | p |}

,

wobei

p

ein haltendes Programm ist und

| p |

die Länge des Programms in Bit bezeichnet.

Literatur

Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik (= Spektrum-Hochschultaschenbuch.). 4. Auflage. Spektrum – Akademischer Verlag, Heidelberg u. a. 1996, ISBN 3-8274-0130-5.
Hans Hermes: Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit. Einführung in die Theorie der rekursiven Funktionen (= Heidelberger Taschenbücher. 87). 2. Auflage. Springer, Berlin u. a. 1971, ISBN 3-540-05334-4.
Arnold Oberschelp: Rekursionstheorie. BI-Wissenschaftlicher-Verlag, Mannheim u. a. 1993, ISBN 3-411-16171-X.
Wolfgang Rautenberg: Einführung in die Mathematische Logik. Ein Lehrbuch. 3., überarbeitete Auflage. Vieweg + Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2.