Growth Rates of Recursive Functions.

How fast can primitive recursive functions grow?

times.

MATH

$\QTR{Large}{4!=24}$

The Ackermann Function. a "simple" recursive, not primitive recursive, function.

The follow version of the Ackermann function is due to Rozar Peter.

The Ackermann-Peter function is defined recursively for non-negative integers $\QTR{Large}{m}$ and $\QTR{Large}{n}$ as follows:

$\vspace{1pt}$

More precisely, The following method computes the Ackermann function:

_____________________________________

_____________________________________

The nesting in the last line leads to grow much faster than

any primitive recursive function could. Here are a few values:

Homework Due Oct 27.

Show