Overview

Ackermann function


Show Summary Details

Quick Reference

The function A defined inductively on pairs of nonnegative integers in the following manner:

A(0,n) = n + 1

A(m+1,0) = A(m,1)

A(m+1,n+1) = A(m,A(m+1,n)) where m,n ≥ 0. Thus

A(1,n) = n + 2

A(2,n) = 2n + 3

A(3,n) = 2n+3 - 3 The highly recursive nature of the function makes it a popular choice for testing the ability of compilers or computers to handle recursion. It provides an example of a function that is general recursive but not primitive recursive because of the exceedingly rapid growth in its value as m increases.

The Ackermann function may also be regarded as a function Ack of a single variable:

Ack(n) = A(n,n)

where A is defined as above.

Subjects: Computing.


Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.