Rekursive Funktionen und algorithmische Berechenbarkeit

Wir hatten die arithmetischen Operationen auf den natürlichen Zahlen rekursiv eingeführt. Als Ausblick betrachten wir nun das Konzept einer rekursiv definierten Funktion noch genauer und gelangen in zwei Stufen zu einer einfachen Definition von „algorithmisch berechenbar“.

Für die erste Stufe benötigen wir Basisfunktionen, Kompositionen und die so genannte primitive Rekursion.

Als Basisfunktionen bezeichnen wir die folgenden Funktionen:

Z : ℕ → ℕ,	Z(n) = 0 für alle n, (Nullfunktion)
S : ℕ → ℕ,	S(n) = n + 1 für alle n, (Nachfolgerfunktion)
I^k_i : ℕ^k → ℕ,	I^k_i(n₁, …, n_k) = n_i für alle n₁, …, n_k, (Projektionen)

wobei die Projektionen für alle k ≥ 1 und alle 1 ≤ i ≤ k definiert sind.

Sind h : ℕ^k → ℕ und g_i : ℕ^k′ → ℕ, 1 ≤ i ≤ k, Funktionen, so ist die Komposition dieser Funktionen, in Zeichen h(g₁, …, g_k), die Funktion f : ℕ^k′ → ℕ mit

f (n₁, …, n_k′) = h(g₁(n₁, …, n_k′), …, g_k(n₁, …, n_k′)) für alle n₁, …, n_k′ .

Seien h : ℕ^k + 1 → ℕ und g : ℕ^k − 1 → ℕ Funktionen für ein k ≥ 1. (Ist k = 1, so fassen wir g als ein Element von ℕ auf.) Dann ist die primitive Rekursion von g und h, in Zeichen rec(g, h), die Funktion f : ℕ^k → ℕ mit:

f (0, p₁, …, p_k − 1)	= g(p₁, …, p_k − 1), (Rekursionsanfang)
f (n + 1, p₁, …, p_k − 1)	= h(n, f (n, p₁, …, p_k − 1), p₁, …, p_k − 1) (Rekursionsschritt)

für alle n und alle „Parameter“ p₁, …, p_k − 1  ∈  ℕ.

Damit können wir nun definieren:

Definition (primitiv rekursive Funktionen)

Die primitiv rekursiven Funktionen sind wie folgt definiert:

(i)	Jede Basisfunktion ist primitiv rekursiv.

(ii)	Eine Komposition h(g₁, …, g_k) primitiv rekursiver Funktionen h, g₁, …, g_k ist primitiv rekursiv.

(iii)

Eine primitive Rekursion rec(g, h) primitiv rekursiver Funktionen g und h ist primitiv rekursiv.

Für ein A ⊆ ℕ^k definieren wir die Indikatorfunktion ind_A : ℕ^k → { 0, 1 } von A durch ind_A(n₁, …, n_k) = 1, falls (n₁, …, n_k)  ∈  A, und ind_A(n₁, …, n_k) = 0, sonst. Damit können wir unseren Rekursionsbegriff auf Relationen übertragen:

Definition (primitiv rekursive Relationen)

Eine Relation A ⊆ ℕ^k, k ≥ 1, heißt primitiv rekursiv, falls ind_A : ℕ^k → ℕ primitiv rekursiv ist.

Es ist leicht zu sehen, dass die Addition, Multiplikation und Exponentiation auf ℕ primitiv rekursiv sind. Allgemeiner kann eine Fülle von Funktionen und Relationen als primitiv rekursiv nachgewiesen werden. Alle primitiv rekursiven Funktionen sind im intuitiven Sinne algorithmisch berechenbar, und konkret können wir die vermöge der Schemata (i) − (iii) vorliegende Definition einer primitiv rekursiven Funktion f : ℕ^k → ℕ einem Computer beibringen und die Werte f(n₁, …, n_k) für beliebige n₁, …, n_k ausrechnen, wenn wir physikalische Limitationen vernachlässigen. Umgekehrt stellt sich die Frage, ob jede durch einen Computer berechenbare Funktion primitiv rekursiv ist. Die Antwort ist nein. Es zeigt sich, dass geschachtelte Rekursionen durch die primitive Rekursion nicht in allen Fällen abgedeckt sind. Ein Beispiel ist die Ackermann-Funktion ac : ℕ² → ℕ, die definiert wird durch

$ac (m, n) = { \begin{matrix} 2 n & falls m = 0, \\ 1 & falls m > 0, n = 0, \\ ac (m - 1, ac (m, n - 1)) & sonst. \end{matrix}$

Der Leser möge sich das enorme Wachstum dieser Funktion vor Augen führen, indem er einige Werte ac(m, n) für kleine m und n berechnet. In der Tat kann man zeigen, dass die Funktion h : ℕ → ℕ mit h(n) = ac(n, n) für alle n schneller wächst als jede primitiv rekursive Funktion. Die Funktionen h und ac sind damit nicht primitiv rekursiv. Andererseits sind diese Funktionen mit Hilfe eines Computers berechenbar.

Ein anderes Beispiel für eine berechenbare, aber nicht primitiv rekursive Funktion erhalten wir durch Diagonalisierung. Wir können alle einstelligen primitiv rekursiven Funktionen auflisten als f₀, f₁, f₂, …, f_n, … Nun definieren wir eine Funktion g : ℕ → ℕ „diagonal“ durch g(n) = f_n(n) + 1 für alle n. Dann ist g ≠ f_n für alle n. Die Funktion g lässt sich, mit etwas Programmieraufwand, tatsächlich mit Hilfe eines Computers berechnen.

Wir müssen also unsere Definition der primitiv rekursiven Funktion erweitern, und im Hinblick auf das sehr allgemeine Diagonalargument muss diese Erweiterung substantiell sein und eine neue Idee ins Spiel bringen. Erstaunlicherweise sind wir aber nur einen Schritt von einer umfassenden Definition entfernt: In Berechnungen können wir eine „unbeschränkte Suche“ starten, die entweder ein Ergebnis liefert oder aber divergiert, d. h. unendlich lange läuft. Diese unbeschränkte Suche fügen wir nun zu den primitiv rekursiven Funktionen hinzu.

Ist g : ℕ^k + 1 → ℕ, k ≥ 1, eine Funktion, so ist die μ-Rekursion von g, in Zeichen μ g, die Funktion f : A → ℕ mit

A = { (n₁, …, n_k) | es gibt ein n mit g(n₁, …, n_k, n) = 0 } ⊆ ℕ^k,

f(n₁, …, n_k) = „das kleinste n mit g(n₁, …, n_k, n) = 0“ für alle (n₁, …, n_k)  ∈  A.

Damit definieren wir nun:

Definition (partiell rekursiv)

Eine Funktion f : A → ℕ, A ⊆ ℕ^k, k ≥ 1, heißt partiell rekursiv, falls es primitiv rekursive Funktionen g : ℕ^k + 1 → ℕ und u : ℕ → ℕ gibt mit f = u ∘ μ g.

Eine partiell rekursive Funktion entsteht also aus einer primitiv rekursiven Funktion durch eine unbeschränkte Nullstellensuche, gefolgt von einer abschließenden primitiv rekursiven Umrechnung der Suchergebnisse (beschrieben durch u).

Der Definitionsbereich einer k-stelligen partiell rekursiven Funktion ist im Allgemeinen eine echte Teilmenge von ℕ^k. Dieses Merkmal verhindert es, die partiell rekursiven Funktionen erneut durch Diagonalisierung zu transzendieren. Wir können diese Funktionen wieder als f₀, f₁, …, f_n, … auflisten, und wir können g : A → ℕ, A ⊆ ℕ, definieren durch g(n) = f_n(n) + 1, falls n  ∈  dom(f_n). Aber wir können nicht mehr „g ≠ f_n für alle n“ folgern, da im Allgemeinen n  ∉  dom(g) gilt.

Gilt dom(f) = ℕ^k für eine k-stellige partiell rekursive Funktion f, so heißt f auch μ-rekursiv oder kurz rekursiv.

Man kann beweisen, dass die partiell rekursiven Funktionen genau mit den Funktionen f : A → ℕ, A ⊆ ℕ^k, k ≥ 1, zusammenfallen, die durch eine beliebig gewählte höhere Programmiersprache im theoretischen Sinne berechnet werden können. Insbesondere sind die Ackermann-Funktion und die Diagonalisierung der primitiv rekursiven Funktionen μ-rekursiv, und die Diagonalisierung der partiell rekursiven Funktionen ist partiell rekursiv.

Insgesamt ist eine Vielzahl von unterschiedlich motivierten Definitionen des Begriffs „algorithmisch berechenbar“ gefunden worden, die allesamt genau die partiell rekursiven Funktionen liefern. Dies ist ein starkes Argument dafür, dass man einen wichtigen und natürlichen Begriff gefunden hat. Dass alle intuitiv berechenbaren Funktionen unter diesen Begriff fallen, lässt sich aufgrund der Unschärfe der intuitiven Berechenbarkeit naturgemäß nicht beweisen. Diese Hypothese ist als Churchsche These bekannt.

Die μ-rekursiven Funktionen bilden nur einen kleinen Teil aller Funktionen auf den natürlichen Zahlen. Denn ihre Menge ist abzählbar, während die Menge aller Funktionen von ℕ nach ℕ überabzählbar ist. Diese Überlegung zeigt die Weite des allgemeinen mathematischen Funktionsbegriffs.