μ-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 {{#invoke:Vorlage:lang|full |CODE=el |SCRIPTING=Grek |SERVICE={{#if: {{#invoke:TemplUtl|faculty| 0 }} | neu}}griechisch |SUITABLE=prefix neu}} ‚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 <math>f\colon\mathbb{N}^{k+1} \to \mathbb{N}</math> und natürliche Zahlen <math>x_1;\dots;x_k \in \N</math> sei die Menge

<math>M(f,x_1,\dots,x_k) = \{n \in \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 \}</math>

festgehalten, also die Gesamtheit aller <math>n</math> derart, dass <math>f</math> an der Stelle <math>(x_1,\dots,x_k,n)</math> identisch 0 verschwindet und zusätzlich für alle Punkte <math>(x_1,\dots,x_k,m)</math> mit <math>m \leq n</math> definiert ist.

Zu beachten ist dabei, dass <math>M(f,x_1,\dots,x_k)</math> als Menge natürlicher Zahlen genau dann ein Minimum besitzt, wenn sie nicht leer ist (vgl. Wohlordnung).

Durch Anwendung des <math>\mu</math>-Operators auf <math>f</math> entstehe nun die partielle Funktion <math>\mu f \colon \N^k \to \N</math>, definiert durch:

<math>\mu f(x_1, \dots, x_k) = \begin{cases} \min M(f,x_1,\dots,x_k), & \text{falls } M(f,x_1,\dots,x_k) \neq \emptyset \\ \text{undefiniert} & \text{sonst} \end{cases}</math>

Insbesondere bildet der Operator <math>\mu</math> also eine <math>(k+1)</math>-stellige partielle Funktion auf eine <math>k</math>-stellige partielle Funktion ab.

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

Parameter: <math>x_1, \ldots, x_k</math>.
Setze <math>n</math> auf <math>0</math>;
Solange <math>f(x_1,\dots,x_k,n) \neq 0</math>, erhöhe <math>n</math> um <math>1</math>;
Ergebnis: <math>n</math>.

Definition der μ-rekursiven Funktionen

Die Klasse <math>Pr</math> der μ-rekursiven Funktionen (<math>\mathbb{N}^k \to \mathbb{N}</math>) umfasst die folgenden Grundfunktionen:

1. konstante 0-Funktion: <math>f^k \left( n_1,\dots, n_k \right) := 0</math>
2. Projektion auf ein Argument: <math>\pi_i^k \left( n_1,\dots, n_k \right) := n_i</math>, <math>1 \le i \le k</math>
3. Nachfolgefunktion: <math>\nu \left( n \right) := n + 1</math>

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

1. der Komposition: <math>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)</math>, falls <math>g, h_1,\dots, h_m \in Pr</math>
2. der primitiven Rekursion: <math>f \left( 0, n_2,\dots, n_k \right) := g \left( n_2,\dots, n_k \right)</math> und <math>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)</math>, falls <math>h, g \in Pr</math>
3. 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 <math>a</math>, <math>b</math>, <math>c</math> darstellen lässt.
Genau so kann eine Funktion <math>h(a,b,c)=y</math> (eine bijektive Abbildung <math>\mathbb{N}^3 \to \mathbb{N}</math>) definiert werden,
die eine geeignete Kodierung der TM ist.

Nehmen wir also eine primitiv-rekursive Funktion

<math>f(n,x)= y</math>,

die eine geeignete Kodierung der TM liefert für die Eingabe <math>x</math> nach <math>n</math> Berechnungsschritten,

und eine zweite primitiv-rekursive Funktion

<math>g(y)=0 \lor g(y)=1</math>,

die für eine Kodierung <math>y</math> als Ergebnis 0 liefert, falls <math>y</math> einen Endzustand der TM repräsentiert, und ansonsten 1.

Dann ergibt

<math>\mathrm{Anzahl}(x)=\mu(g(f(n,x)))</math>

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

<math>\mathrm{Berechnung}(x)=f(\mathrm{Anzahl}(x), x)</math>

die Berechnung der TM in einem Endzustand bei der Eingabe <math>x</math>.

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 <math>\Omega</math>) ist nicht μ-rekursiv. Die Halte-Wahrscheinlichkeit ist definiert durch

<math>\Omega:=\sum_{p}2^{-\left|p\right|}</math>,

wobei <math>p</math> ein haltendes Programm ist und <math>\left| p\right|</math> 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.
• {{#invoke:Vorlage:Literatur|f}}