Ackermannfunktion

Definition

$$a:{\mathbb{N}}^2\to \mathbb{N}$$

$$a(0,m)=m+1$$

$$a(n+1,0)=a(n,1)$$

$$a(n+1,m+1)=a(n,a(n+1,m))$$

Einige Funktionswerte

Satz

• Die Ackermannfunktion "wächst schneller" als jede primitiv rekursive Funktion
• Die Ackermannfunktion ist nicht LOOP berechenbar / nicht primitiv rekursiv
• Die Ackermannfunktion ist total (überall definiert)

Beweis

Für den Beweis, dass die Ackermannfunktion nicht primitiv rekursiv ist, geht man wie folgt vor:

• Definiere zu jeder primitiv rekursiven Funktion $$f$$ eine Funktion

  $$m(n,f)=\max \text{{}f(\overrightarrow{(}x))|\Sigma \overrightarrow{(}x)\le n\text{}}$$

• Zeige, dass