Ensemble Collections

TITLE	Ackermann function
SUBJECT	msc:03D75
SUBJECT	mathematics
DESCRIPTION	Ackermann's function ... is defined by the recurrence relations ... 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 ... 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 <i>z</i>-fold exponentiation of <i>x</i> with <i>y</i> 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.
PUBLISHER	PlanetMath
DATE	2004-03-30
TYPE	text
FORMAT	text/html
IDENTIFIER	planetmath:92
SOURCE	http://planetmath.org/encyclopedia/AckermannFunction.html
LANGUAGE	en-us