Ackermann function
Ackermann function 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. Named for W. Ackermann, 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.
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. Named for W. Ackermann, 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.
More From encyclopedia.com
You Might Also Like
NEARBY TERMS
Ackermann function