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
Hindustan , Hindustan •Abadan, Abidjan, Amman, Antoine, Arne, Aswan, Avon, Azerbaijan, Baltistan, Baluchistan, Bantustan, barn, Bhutan, Dagestan, darn, dewan, Fa… Holstein , Holstein •airplane, terreplein •sailplane, tailplane •mainplane •seaplane, ski-plane •chilblain •biplane, triplane •warplane • towplane • Tamerlane •… Mahon , Mahon •Abadan, Abidjan, Amman, Antoine, Arne, Aswan, Avon, Azerbaijan, Baltistan, Baluchistan, Bantustan, barn, Bhutan, Dagestan, darn, dewan, Farne,… Huascaran , Huascarán •Abadan, Abidjan, Amman, Antoine, Arne, Aswan, Avon, Azerbaijan, Baltistan, Baluchistan, Bantustan, barn, Bhutan, Dagestan, darn, dewan, Fa… Primitive Recursion , primitive recursive function A function that can be obtained from certain initial functions by a finite number of applications of composition and pri… N , N, n [Called ‘en’]. The 14th LETTER of the Roman ALPHABET as used for English. It originated as the Phoenician symbol nun, adopted by the Greeks as n…
You Might Also Like
NEARBY TERMS
Ackermann function