3.3 Primitive Rekursion kann nicht alles: die Péter-Ackermann-Funktion

In den vorhergehenden Teilkapiteln haben wir gesehen, dass Sie allerhand mit primitiv rekursiven Funktionen implementieren können. Darunter Dinge, die komplexere Rekursion oder Schleifen mit mehreren lokalen Variablen zu brauchen scheinen (wie die Fibonacci-Zahlen), ja sogar Dinge, die über den Bereich der natürlichen Zahlen hinausgehen, wie zum Beispiel das Sortieren eines beliebig langen Arrays. Kernpunkt war die Erkenntnis, dass wir komplexere "Datenstrukturen" wie Paare von natürlichen Zahlen als eine natürliche Zahl codieren können und somit der primitiven Rekursion zugänglich machen können.

Es liegt also Nahe, zu vermuten, dass primitive Rekursion bereits den Berechenbarkeitsbegriff zufriedenstellend formalisiert: das also alles "Berechenbare" auch primitiv rekursiv sei. Der Wikipedia-Artikel über die Ackermann-Funktion schreibt, dass der deutsche Mathematiker David Hilbert dies auch vermutete. Im Jahre 1926 jedoch definierte Wilhelm Ackermann eine Funktion, die "offensichtlich berechenbar", jedoch nicht primitiv rekursiv ist. Die Funktion, die wir heute die Ackermann-Funktion nennen, ist allerdings eine vereinfachte Version, die 1935 von der ungarischen Mathematikerin Rózsa Péter gefunden wurde (obwohl der letztere Artikel das Jahr 1955 nennt).

Definition (Péter-Ackermann-Funktion). \begin{align*} A(m,n) & := \begin{cases} n+1 & \textnormal{ if $m=0$,} \\ A(m-1,1) & \textnormal{ if $m \geq 1, n=0$} \\ A(m-1, A(m,n-1)) & \textnormal{ if $m,n \geq 1$} \ . \end{cases} \end{align*} Manchmal sehen Sie in der Literatur auch die äquivalente, vielleicht lesbarere Definition: \begin{align*} A(0,n) & := n+1 \\ A(m+1, 0) & := A(m,1) \\ A(m+1, n+1) & := A(m, A(m+1,n)) \end{align*} Für festes $m\in \N$ schreiben wir auch $A_m$ für die ein-parametrige Funktion \begin{align*} A_m : & \N \rightarrow \N \\ n & \mapsto A(m,n) \ . \end{align*}

Es lohnt sich, diese Funktion für kleine Werte von $m$ zu untersuchen. Aus der Definition geht unmittelbar hervor, dass $A_0(n) = n+1$ ist. Für $A_1 (n)$ rechnen wir \begin{align*} A_1 (n) & = A_0 ( A_1 (n-1)) = A_0 (A_0(A_1(n-2))) = \dots = \underbrace{A_0 (A_0 (...(A_0}_{i \textnormal{ mal}}(A_1(n-i)))...)) \\ & = \underbrace{A_0 (A_0 (...(A_0}_{n \textnormal{ mal}}(A_1(0)))...)) \\ & = \underbrace{A_0 (A_0 (...(A_0}_{n+1 \textnormal{ mal}}(1))...)) \\ & = n+2 \ . \end{align*} Soweit schaut die Funktion nicht besonders beindruckend aus. $A_2$ bekommen iwr nach dem gleichen Schema: \begin{align*} A_2 (n) & = \underbrace{A_1 (A_1 (...(A_1}_{n+1 \textnormal{ mal}}(1))...)) \ , \\ \end{align*} wir fangen also mit $1$ an und zählen $n+1$ mal eine 2 drauf. Wir erhalten $2n + 3$, also \begin{align*} A_2 (n) & = 2n + 3 \ . \end{align*} $A_3$ wird etwas unangenehmer, weil wir keine gute Intuition haben, was "$n+1$ mal verdoppeln und jedes Mal 3 draufzählen" ergibt. Mit 1 beginnend erhalten wir also \begin{align*} 1 \stackrel{A_2}{\rightarrow} 5 \stackrel{A_2}{\rightarrow} 13 \stackrel{A_2}{\rightarrow} 29 \stackrel{A_2}{\rightarrow} 61 \stackrel{A_2}{\rightarrow} 125 \end{align*} Das ist schon genug, um eine Vermutung zu formulieren: $A_3(n) = 2^{n+3} - 3$ und diese dann per Indution zu beweisen.

Die Péter-Ackermann-Funktion ist berechenbar

Theorem Sei $m \in \N$ gegeben. Die Funktion $A_m$ ist primitiv rekursiv.

Beweis. Wir verwenden Induktion über $m$. Für $m=0$ gilt $A_0(n)= n+1$ und somit $A_0 = \succ$. Sei nun also $m \geq 1$. Wir sehen, dass \begin{align*} A_m(t) = A_{m-1} (A(m,t-1)) \ . \end{align*} Ich schreibe nun $t$ anstatt $n$ als Parameter, um mich der Notation der primitiven Rekursion anzunähern. Wir wissen bereits, dass $A_{m-1}$ primitiv rekursiv ist. Wir können $A_m(t)$ also schreiben als \begin{align*} A_m(t) & = \begin{cases} A_{m-1} (1) & \textnormal{ if $t=0$} \\ A_{m-1} (A_m(t-1)) & \textnormal{ if $t \geq 1$.} \end{cases} \end{align*} Wir können also $h = \comp (A_{m-1}, \pi^3_1)$ wählen. Was ist $g$? Der Startwert soll $g(\vec{x})$ sein, wir haben aber kein $\vec{x}$, bzw. dies ist der "leere Vektor". Wir brauchen eine Funktion $C$, die null Argumente nimmt und $A_{m-1}(1)$ zurückgibt. Also: $g = \comp(A_{m-1}, {\rm one})$. Wir könnten sogar noch frecher sein und $g = \comp(\succ, \comp(\succ, \comp(... \comp(\succ, \zero))))$ schreiben, einfach $A_{m-1}(1)$ mal hintereinander; diesen Wert also hard-coden. Allerdings ist die erste Variante einfacher, und somit \begin{align*} A_m & = \primrec(\comp (A_{m-1}, {\rm one}), \comp (A_{m-1}, \pi^3_1)) \ . \end{align*} Wir sehen also: jedes $A_m$, betrachtet als Funktion mit einem Eingabeparameter, ist primitiv rekursiv. $\square$

Wir haben also gezeigt, dass jedes $A_m$ primitiv rekursiv ist. Heißt das auch, dass die zwei-parametrige Funktion $A(m,n)$ berechenbar ist? In der primitiven Rekursion haben wir keine Möglichkeit, den Index $m$ als Eingabewert zu lesen und dann aus dem unendlichen Array primitiv rekursiver Funktionen $[A_0, A_1, A_2, \dots]$ den Eintrag $A_m$ auszulesen. Aber berechenbar in einem ganz allgemeinen Sinn? Diese Frage können wir zu diesem Zeitpunkt nicht formal beantworten, weil wir den Begriff allgemeiner Berechenbarkeit noch gar nicht definiert haben. Es ist allerdings an der Definition von $A(m,n)$ nichts magisches, und intuitiv würden wir sagen, dass es klar berechenbar ist; so wie wir ja auch leicht eine Funktion implementieren könnten, die $A(m,n)$ berechnet.

Die Ackermann-Péter-Funktion ist nicht primitiv rekursiv

Theorem Die Ackermann-Péter-Funktion ist nicht primitiv rekursiv.

Mein Beweis paraphrasiert im Wesentlichen den auf planetmath.org

Die Aussage verstehen. Beachten Sie, dass Theorem 3.3.3 nicht mit Theorem 3.3.2 im Widerspruch steht. Theorem 3.3.3 besagt, dass $A_m$ primitiv rekursiv ist, für jedes $m$. Die Zahl $m$ ist hier also Teil der Aussage, nicht Eingabeparameter der Funktion; die Funktion $A_m$ hat nur einen Eingabeparameter. Theorem 3.3.3 hingegen macht eine Aussage über eine Funktion $A(m,n)$ mit zwei Eingabeparametern, und $m$ ist nun einer dieser beiden.

Anders ausgedrückt: sie können zwar jedes einzelne $A_m$ in der "Programmiersprache" der primitiven Rekursion implementieren, allerdings brauchen Sie für jedes $m$ neuen Code. Sie können keinen Code schreiben, der, gegeben $m$, den Code für $A_m$ irgendwie implizit produziert und dann mit $n$ aufruft. Jedenfalls nicht in der Programmiersprache der primitiven Rekursion.

Beweisidee. Für jedes feste $m$ ist die ein-parametrige Funktion $A_m := n \mapsto A(m,n)$ primitiv rekursiv und kann als Funktion mit $m$ verschachtelten for-Schleifen betrachtet werden. Es wird sich herausstellen, dass $A_m$ in gewisser Weise die am schnellsten wachsende aller solcher Funktionen ist. Wäre also $A(m,n)$ primitiv-rekursiv, dann könnten wir es mit $d$ verschachtelten for-Schleifen berechnen; was ein Widerspruch ist, weil bereits $A_{d+1}$ schneller wächst als jede primitiv-rekursive Funktion mit $d$ verschachtelten Schleifen.

Beweis. Wir brauchen eine robuste Definition, was es heißt, dass eine Funktion $f: \N \rightarrow \N $ schneller wächst als $g: \N^k \rightarrow \N$.

Definition. Sei $f: \N \rightarrow \N$ und $g: \N^k \rightarrow \N$. Die Funktion $f$ majorisiert $g$, wenn \begin{align*} f (\max(x_1,\dots,x_k) \gt g(x_1, \dots, x_k) \ . \end{align*} für alle $x_1,\dots,x_k \in \N$ gilt. Wir schreiben auch kurzerhand $f \gt g$.

Sei zum Beispiel $g(x,y) = x \cdot y$ und $f(x) = 2^x$. Dann majorisiert $2^x$ die Funktion $x \cdot y$ nicht; sei beispielsweise $(x,y) = (3,2)$, dann ist $g(x,y)=6$ aber $f(\max(3,2)) = 2^3 = 8$. Allerdings majorisiert $2^x + 2$ die Funktion $x+y$, ganz allgemein weil $2^x + 2 \gt x^2$ für alle $x \in \N$ gilt. Wir werden nun zeigen, dass jede primitiv rekursive Funktion $g: \N^k \rightarrow \N$ von einem $A_r$ majorisiert wird; hierbei ist wichtig, dass der Index $r$ als Konstante betrachtet wird, also von der "Bauweise" von $g$ abhängen darf, nicht aber von den Eingabewerten, die $g$ bekommt.

Lemma Für jede primitiv rekursive Funktion $f: \N^k \rightarrow \N$ gibt es ein $r \in \N$, so dass $f$ von $A_r$ majorisiert wird.

Aus diesem Lemma folgt dann, dass $A(m,n)$ selbst nicht primitiv rekursiv sein kann. Wäre es dies, dann gäbe es ja ein $r$, so dass das ein-parametrige $A_r$ die zwei-parametrige Funktion $A(m,n)$ majorisieren würde: \begin{align*} A_r (\max(m,n)) \gt A(m,n) \end{align*} für alle Werte $m,n \in \N$ und somit insbesondere \begin{align*} A_r (r) \gt A(r,r) \ , \end{align*} was offensichtlich ein Widerspruch ist, da beide Seiten gleich sind.

Wir werden nun das Lemma beweisen. Wir verwenden Induktion über die Weise, in der die Funktion $f$ konstruiert worden ist, also über die Anzahl der Comp- und PrimRec-Kombinatoren, die wir zum Bau von $f$ gebraucht haben. Im folgenden schreiben wir, wenn wir einen Vektor $\vec{x} = (x_1,\dots,x_n)$ aus natürlichen Zahlen haben, oft $x := \max(x_1,\dots,x_n)$.

Induktionsbasis. Wir betrachten wir die Basisfunktionen $\zero, \succ, \pi^n_k$. Wir wissen bereits, dass $A_0(n) = n+1$ ist, also $A_0 = \succ$. Leider majorisiert $A_0$ also $\succ$ nicht. Wie steht es mit $A_1$? Es gilt $A_1(n) = n+2$, und somit ist \begin{align*} \zero(\vec{x}) & = 0 \lt 1 \lt A_1(x) \\ \succ(x) & = x+1 \lt x+2 = A_1(x) \\ \pi^n_k (\vec{x}) & = x_k \leq x \lt x + 2 = A_1(x) \ , \end{align*} wobei wir die Schreibweise $x = \max(\vec{x}) = \max(x_1,\dots,x_n)$ verwenden. Wir schlussfolgern: $A_2$ majorisiert jede Basisfunktion.

Induktionsschritt. Wenn $f$ keine Basisfunktion ist, dann wurde $f$ mittels Komposition oder primitiver Rekursion konstruiert. Für jeden Fall führen wir eine getrennte Rechnung durch.

Komposition: $f(\vec{x}) = g(h_1(\vec{x}), \dots, h_k(\vec{x}))$, für primitiv rekursive Funktionen $g, h_1, \dots, h_k$. Jede dieser Funktionen wurde mit weniger Kombinatoren konstruiert; somit wird jede dieser Funktionen von einem $A_r$ majorisiert: $A_r \gt g, A_{s_1} \gt h_1, \dots, A_{s_k} \gt h_k$. Für einen Eingabevektor $\vec{x}$ schreiben wir $x := \max(x_1,\dots,x_n)$ und rechnen: \begin{align*} f(\vec{x}) & = g(h_1(\vec{x}), \dots, h_k(\vec{x})) \\ & \lt A_r (\max (h_1(\vec{x}), \dots, h_k(\vec{x}))) \tag{weil $A_q \gt g$} \\ & \leq A_r ( \max (A_{s_1}(x), A_{s_2}(x), \dots, A_{s_k}(x))) \tag{weil $A_r$ monoton und $A_{s_i} \gt h_i$} \end{align*} Wir setzen nun $q := \max(r, s_1, \dots, s_k)$. Dann ist der obige Wert höchstens: \begin{align*} \dots & \leq A_q (A_q(x)) \\ & \leq A_{q} (A_{q+1} (x)) = A_{q+1} (x+1) \ . \end{align*} Schlussendlich behaupte ich, dass $A_{q+1}(x+1) \leq A_{q+2}(x)$ gilt: \begin{align*} A_{q+2}(x) & = A_{q+1} (A_{q+2}(x-1)) \geq A_{q+1} (A_2 (x-1)) = A_{q+1} (x+1) \ . \end{align*} Also: $A_{q+2}$ majorisiert $f$.

Primitive Rekursion: $f = \primrec (g,h)$, also \begin{align*} f(t, \vec{x}) & = \begin{cases} g(\vec{x}) & \textnormal{ if $t=0$} \\ h(f(t-1,\vec{x}), t-1, \vec{x}) & \textnormal{ if $t \geq 1$} \end{cases} \ , \end{align*} wobei $g, h$ bereits mit weniger Kombinatoren konstruierte primitiv rekursive Funktionen sind. Daher gibt es ein $q \in \N$ mit $A_q \gt g$ und $A_q \gt h$.

Behauptung $f(t, \vec{x}) \leq A_{q+1} (t+x)$, wobei $x = \max(\vec{x}) = \max(x_1,\dots,x_n)$.

Beweis. Wir verwenden Induktion über $t$. Wenn $t=0$ ist, dann gilt \begin{align*} f(0,\vec{x}) & = g(\vec{x}) \lt A_q (x) \leq A_{q+1} (x) \ . \end{align*} Wenn $t \geq 1$ ist, dann gilt \begin{align*} \hspace{-3cm} f(t, \vec{x}) &= h(f(t-1,\vec{x}), t-1, \vec{x}) \\ & \lt A_{q} (\max(f(t-1, \vec{x}), t-1, x_1, \dots, x_n)) \tag {weil $A_q \gt h$} \\ & \lt A_{q} (\max(f(t-1, \vec{x}), t-1, x)) \tag {für $x := \max(x_1,\dots,x_n)$} \\ & \leq A_q (\max(A_{q+1} (t-1+x), t-1, x)) \tag{ per Induktionshypothese für $t-1$} \\ & = A_q (A_{q+1}(t-1+x)) % \tag{weil $\max(t-1,x) \leq t-1+x \leq A_{q+1}(t-1+x)$} \\ & = A_{q+1}(t+x) \ . \end{align*} Somit ist die Behauptung bewiesen. $\square$

Die Behauptung reicht aber noch nicht, da die rechte Seite der Ungleichung $f(t,\vec{x}) \lt A_{q+1}(t+x)$ eine Funktion in zwei Parametern ist: $t$ und $x$, wir aber für das zu beweisende Lemma aber eine Funktion in einem Parameter brauchen, nämlich $\max(t, \vec{x})$. Sei also $z := \max(t,x) = \max(t, x_1,\dots,x_n)$. Dann gilt

\begin{align*} A_{q+1} (x+t) & \leq A_{q+1} (2z) \leq A_{q+1} (2(z-1) + 3) \\ & = A_{q+1} (A_2(z-1)) \tag{da $A_2(n) = 2n+3$}\\ & \leq A_{q+1} (A_{q+2}(z-1)) \\ & = A_{q+2}(z) \ . \end{align*} Es gilt also $A_{q+2} \gt f$ und das Lemma ist bewiesen. $\square$

In der Vorlesung am 7. Mai 2024 hatte ich den Grad einer primitiv-rekursiven Funktion definiert. Das ist in etwa die "Verschachtelungstiefe" von $f$. Betrachten wir beispielsweise die Funktion $\pair(x,y) = {x + y + 1 \choose 2} + x$ und dröseln auf, wie wir diese als primitiv-rekursive Funktion konstruiert haben:

pair = Comp(add, p0, Comp(choose2,Comp(add,p0,Comp(succ,p1))))
choose2 = PrimRec(zero, Comp(add,p0,p1))
add = PrimRec (p0, Comp(succ, p0))

dann können wir das auf Baum darstellen: