ENCYCLOPEDIA 4U .com

 Web Encyclopedia4u.com

# Ackermann function

The Ackermann function (also known as Ackermann-Peter function), an important example in the theory of computation, is a recursive function which takes two natural numbers as arguments and returns a natural number as its value.

 Table of contents 1 Definition 2 Recursive, but not primitive recursive 3 Explicit description 4 History 5 Inverse

## Definition

A(0, n) = n + 1    for n ≥ 0
A(m, 0) = A(m - 1, 1)    for m ≥ 1
A(m, n) = A(m - 1, A(m, n - 1))    for m, n ≥ 1

## History

In 1928, Wilhelm Ackermann considered a function A(m, n, p) of three variables, the p-fold iterated exponentiation of m with n, and proved that it is a recursive function which is not primitive recursive. This definition was later simplified by Rosza Peter and Raphael Robinson to the two-variable definition given above.

## Inverse

Content on this web site is provided for informational purposes only. We accept no responsibility for any loss, injury or inconvenience sustained by any person resulting from information published on this site. We encourage you to verify any critical information with the relevant authorities.