PlanetMath: Ackermann function

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (200)
Orphanage
Unclass'd
Unproven (511)
Corrections (9)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

Ackermann function

(Definition)

Ackermann's function is defined by the recurrence relations

	$\displaystyle A(0,y)$	$\displaystyle = y + 1$
	$\displaystyle A(x+1,0)$	$\displaystyle = A(x,1)$
	$\displaystyle A(x+1,y+1)$	$\displaystyle = A(x,A(x+1,y))$

Ackermann's function is an example of a recursive function that is not primitive recursive, but is instead $\mu$ -recursive (that is, Turing-computable).

Ackermann's function grows extremely fast. In fact, we find that

$\displaystyle A(0,y)$	$\displaystyle =$	$\displaystyle y + 1$
$\displaystyle A(1,y)$	$\displaystyle =$	$\displaystyle 2+(y+3) -3$
$\displaystyle A(2,y)$	$\displaystyle =$	$\displaystyle 2\cdot (y+3) - 3$
$\displaystyle A(3,y)$	$\displaystyle =$	$\displaystyle 2^{y+3} - 3$
$\displaystyle A(4,y)$	$\displaystyle =$	$\displaystyle 2^{2^{{\ldotp\cdotp}^2}} - 3 \;\;\;\; (y + 3$ exponentiations $\displaystyle )$
$\displaystyle \cdots$

... and at this point conventional notation breaks down, and we need to employ something like Conway notation or Knuth notation for large numbers.

Ackermann's function wasn't actually written in this form by its namesake, Wilhelm Ackermann. Instead, Ackermann found that the -fold exponentiation of with was an example of a recursive function which was not primitive recursive. Later this was simplified by Rosza Peter to a function of two variables, similar to the one given above.

"Ackermann function" is owned by akrowne.

(view preamble)

Log in to rate this entry.
(view current ratings)

Cross-references: similar, variables, function, Rosza Peter, numbers, Knuth notation, Conway notation, point, Turing-computable, recursive, primitive, recursive function, recurrence relations
There are 2 references to this entry.

This is version 6 of Ackermann function, born on 2002-03-23, modified 2004-03-30.
Object id is 2799, canonical name is AckermannFunction.
Accessed 6897 times total.

Classification:

AMS MSC:

03D75 (Mathematical logic and foundations :: Computability and recursion theory :: Abstract and axiomatic computability and recursion theory)

Pending Errata and Addenda

None.[ View all 2 ]

Discussion

forum policy

Interact