Μ-Rekursion

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

μ-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\leq i\leq 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}}$

Einfach gehalten heißt das, dass μf(x) das kleinste y mit f(y,x) = 0 ist, so dass f(y',x) definiert ist für alle y' < y.

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

Simulation der TM mit μ-Rekursiven Funktionen

TM= Turing Maschine

Es lässt sich Beweisen dass eine TM durch die μ-Rekursiven 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-Idee für die Simulation der TM mit μ-Rekursiven Funktionen:

Man kann zeigen, dass sich die Konfiguration einer TM durch 3 Zahlen a,b,c darstellen lässt. Genau so kann eine Funktion $h(a,b,c)=y$ (eine bijektive Abbildung $N^{3}->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.

Eine zweite Primitiv-Rekursive Funktion $g(y)=0oder1$ die für eine Kodierung $y$ als Ergebnis 0 liefert falls $y$ einen Endzustand der TM representiert, und ansonsten 1.

dann ergibt $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 $Berechnung(x)=f(Anzahl(x),x)$ die Berechnung der TM in einem Endzustand bei der Eingabe $x$.