Direkt zum Inhalt

Lexikon der Mathematik: Ackermann-Funktion

eine von W. Ackermann 1928 angegebene Funktion auf ℕ0, die total berechenbar, aber nicht primitiv-rekursiv ist. Die ursprünglich dreistellige Funktion wurde später noch vereinfacht und hat inzwischen die folgende Form.

Die Definition erfolgt induktiv. Die Funktion a : ℕ02 → ℕ0 sei definiert durch \begin{eqnarray}a(0,y) := y+1,\\ a(x+1,0) := a(x,1),\text{sowie}\\ a(x+1,y+1) := a(x,a(x+1,y)).\end{eqnarray}

Die Funktion a ist nicht primitiv-rekursiv. Dies ergibt sich daraus, daß a(n, n) stärker wächst als jede einstellige primitiv-rekursive Funktion.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos