Μ-Rekursion

Grundidee und Bedeutung

μ-rekursive, auch partiell-rekursive Funktionen bilden die Klasse Pr. Sie sind in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, wichtig, weil sie nach der Church-Turing-These alle Funktionen beschreiben, die im intuitiven Sinn berechenbar sind.

Die Klasse stimmt genau mit den Turing-berechenbaren Funktionen überein. Gleich mächtige Berechenbarkeitsmodelle sind außerdem Lambda-Kalkül, Registermaschinen und WHILE-Programme.

Im Unterschied zu primitiv-rekursiven Funktionen können μ-rekursive Funktionen partiell sein: Für manche Eingaben liefern sie keinen Wert. Die primitiv-rekursiven Funktionen sind eine echte Teilmenge von Pr und stets total, also für jede Eingabe definiert. Jede primitiv-rekursive Funktion ist daher auch μ-rekursiv. Die Ackermannfunktion ist dagegen total und μ-rekursiv, aber nicht primitiv-rekursiv.

Der μ-Operator als Suche

Für eine partielle Funktion f: ℕ^(k+1) → ℕ und x₁, …, xₖ ∈ ℕ wird definiert:

M(f,x₁,…,xₖ) = {n ∈ ℕ | f(x₁,…,xₖ,n) = 0 ∧ ∀ 0 ≤ m ≤ n: f(x₁,…,xₖ,m)↓}.

Diese Menge enthält genau die n, bei denen f den Wert 0 hat und zugleich für alle vorherigen und den aktuellen Suchwert m definiert ist. Ist M nicht leer, besitzt sie wegen der Wohlordnung der natürlichen Zahlen ein Minimum.

Der μ-Operator erzeugt daraus die partielle Funktion μf: ℕ^k → ℕ:

μf(x₁,…,xₖ) = min M(f,x₁,…,xₖ), falls M(f,x₁,…,xₖ) ≠ ∅; andernfalls ist μf undefiniert.

Der Operator macht aus einer (k+1)-stelligen partiellen Funktion eine k-stellige partielle Funktion. Er sucht also den kleinsten passenden Wert n. Praktisch entspricht dies einer While-Schleife: n wird bei 0 gestartet und so lange um 1 erhöht, wie f(x₁,…,xₖ,n) ≠ 0 gilt. Gibt es keinen passenden Wert oder endet eine benötigte Berechnung nicht, kann die Suche nicht terminieren.

Aufbau der Funktionsklasse

Pr enthält als Grundfunktionen die konstante 0-Funktion f^k(n₁,…,nₖ) := 0, die Projektion πᵢ^k(n₁,…,nₖ) := nᵢ für 1 ≤ i ≤ k sowie die Nachfolgefunktion ν(n) := n + 1.

Aus diesen Funktionen entstehen alle μ-rekursiven Funktionen durch drei Abschlussoperationen:

• Komposition: f(n₁,…,nₖ) := g(h₁(n₁,…,nₖ),…,hₘ(n₁,…,nₖ)), wenn g,h₁,…,hₘ ∈ Pr.
• Primitive Rekursion: f(0,n₂,…,nₖ) := g(n₂,…,nₖ) und f(n₁+1,n₂,…,nₖ) := h(f(n₁,…,nₖ),n₁,…,nₖ), wenn h,g ∈ Pr.
• Anwendung des μ-Operators.

Die ersten beiden Konstruktionsarten gehören auch zum Aufbau primitiv-rekursiver Funktionen. Erst der μ-Operator führt die Möglichkeit ein, dass eine Funktion für Eingaben undefiniert bleibt.

Beziehung zur Turingmaschine

Eine Turingmaschine (TM) kann durch μ-rekursive Funktionen simuliert werden; umgekehrt entspricht die Menge der μ-rekursiven Funktionen genau der Menge der Turing-berechenbaren Funktionen.

In der Beweisskizze wird eine TM-Konfiguration durch drei Zahlen a, b, c dargestellt. Eine bijektive Abbildung h(a,b,c) = y von ℕ³ nach ℕ kodiert eine solche Konfiguration. Es gibt eine primitiv-rekursive Funktion f(n,x) = y, die für die Eingabe x die Kodierung der TM nach n Berechnungsschritten liefert. Eine weitere primitiv-rekursive Funktion g(y) liefert 0, wenn y einen Endzustand repräsentiert, und sonst 1.

Damit gibt Anzahl(x) = μ(g(f(n,x))) die Zahl der Schritte bis zum Ende der Berechnung an. Anschließend liefert Berechnung(x) = f(Anzahl(x),x) die kodierte Berechnung im Endzustand.

Folgen und Beispiele

Bei μ-rekursiven Funktionen bezieht sich Berechenbarkeit nur auf Werte im Definitionsbereich. Es gibt kein allgemeines Verfahren, das alle Werte bestimmt, die nicht zu diesem Definitionsbereich gehören. Der μ-Operator beschreibt daher einen Suchprozess, der genau dann abbricht, wenn der gesuchte Wert existiert.

Beispiele:

• Alle primitiv-rekursiven Funktionen sind μ-rekursiv.
• Ackermannfunktion und Sudanfunktion sind totale μ-rekursive, aber nicht primitiv-rekursive Funktionen.
• Die Funktion Fleißiger Biber (busy beaver) ist nicht μ-rekursiv.
• Auch die Ziffernfolge der Halte-Wahrscheinlichkeit, der Chaitinschen Konstante Ω, ist nicht μ-rekursiv. Dabei gilt Ω := Σₚ 2^(-|p|), wobei p ein haltendes Programm und |p| seine Länge in Bit ist.