de.wikipedia.org

μ-Rekursion – Wikipedia

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.

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

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.

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 {\displaystyle a}, {\displaystyle b}, {\displaystyle c} darstellen lässt.
Genau so kann eine Funktion {\displaystyle h(a,b,c)=y} (eine bijektive Abbildung {\displaystyle \mathbb {N} ^{3}\to \mathbb {N} }) definiert werden,
die eine geeignete Kodierung der TM ist.

Nehmen wir also eine primitiv-rekursive Funktion

{\displaystyle f(n,x)=y},

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

und eine zweite primitiv-rekursive Funktion

{\displaystyle g(y)=0\lor g(y)=1},

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

Dann ergibt

{\displaystyle \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

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

die Berechnung der TM in einem Endzustand bei der Eingabe {\displaystyle x}.

  • 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.
{\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.