μ-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 ${\displaystyle f\colon \mathbb {N} ^{k+1}\to \mathbb {N} }$ und natürliche Zahlen ${\displaystyle x_{1};\dots ;x_{k}\in \mathbb {N} }$ sei die Menge

${\displaystyle M(f,x_{1},\dots ,x_{k})=\{n\in \mathbb {N} \mid f(x_{1},\dots ,x_{k},n)=0\ \land \ \forall 0\leq m\leq n\colon f(x_{1},\dots ,x_{k},m)\downarrow \}}$

festgehalten, also die Gesamtheit aller ${\displaystyle n}$ derart, dass ${\displaystyle f}$ an der Stelle ${\displaystyle (x_{1},\dots ,x_{k},n)}$ identisch 0 verschwindet und zusätzlich für alle Punkte ${\displaystyle (x_{1},\dots ,x_{k},m)}$ mit ${\displaystyle m\leq n}$ definiert ist.

Zu beachten ist dabei, dass ${\displaystyle 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 ${\displaystyle \mu }$-Operators auf ${\displaystyle f}$ entstehe nun die partielle Funktion ${\displaystyle \mu f\colon \mathbb {N} ^{k}\to \mathbb {N} }$ definiert durch:

${\displaystyle \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 ${\displaystyle \mu }$ also eine ${\displaystyle (k+1)}$-stellige partielle Funktion auf eine ${\displaystyle k}$-stellige partielle Funktion ab.

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

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

Definition der μ-rekursiven Funktionen

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

1. konstante 0-Funktion: ${\displaystyle f^{k}\left(n_{1},\dots ,n_{k}\right):=0}$
2. Projektion auf ein Argument: ${\displaystyle \pi _{i}^{k}\left(n_{1},\dots ,n_{k}\right):=n_{i}}$, ${\displaystyle 1\leq i\leq k}$
3. Nachfolgefunktion: ${\displaystyle \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: ${\displaystyle 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 ${\displaystyle g,h_{1},\dots ,h_{m}\in Pr}$
2. Die Primitive Rekursion: ${\displaystyle f\left(0,n_{2},\dots ,n_{k}\right):=g\left(n_{2},\dots ,n_{k}\right)}$ und ${\displaystyle 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 ${\displaystyle h,g\in Pr}$
3. Der μ-Operator.

Ä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.

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 ${\displaystyle \Omega }$) ist nicht μ-rekursiv. Die Halte-Wahrscheinlichkeit ist definiert durch ${\displaystyle \Omega :=\sum _{p}2^{-\left|p\right|}}$, wobei ${\displaystyle p}$ ein haltendes Programm ist und ${\displaystyle \left|p\right|}$ 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.