Difference between revisions of "Manuals/calci/ACKERMANN"
Jump to navigation
Jump to search
| Line 7: | Line 7: | ||
*Its arguments are never negative and it always terminates. | *Its arguments are never negative and it always terminates. | ||
*One common version, the two-argument Ackermann–Péter function, is defined as follows: | *One common version, the two-argument Ackermann–Péter function, is defined as follows: | ||
| − | <math>A(m,n) = \begin{cases} n+1 if m=0 \\ | + | |
| − | A(m-1,1) & \mbox {if} m>0 and n=0 \\ | + | <math>A(m,n) = \begin{cases} n+1 \mbox {if} \mbox {m=0} \\ |
| − | A(m-1,A(m,n-1))& \mbox {if} m>0 and n>0 | + | A(m-1,1) & \mbox {if} \mbox {m>0} and \mbox {n=0} \\ |
| − | \end{cases}</math> | + | A(m-1,A(m,n-1))& \mbox {if} \mbox {m>0} and \mbox {n>0} |
| + | \end{cases} </math> | ||
for nonnegative integers m and n. | for nonnegative integers m and n. | ||
*Its value grows rapidly, even for small inputs. | *Its value grows rapidly, even for small inputs. | ||
Revision as of 14:05, 21 September 2016
ACKERMANN(m,n)
- and are the positive integers.
and 
are the positive integers.Description
- The Ackermann function is a classic example of a recursive function, notable especially because it is not a primitive recursive function.
- All primitive recursive functions are total and computable, but the Ackermann function illustrates that not all total computable functions are primitive recursive.
- Its arguments are never negative and it always terminates.
- One common version, the two-argument Ackermann–Péter function, is defined as follows:
Failed to parse (unknown function "\begin{cases}"): {\displaystyle A(m,n) = \begin{cases} n+1 \mbox {if} \mbox {m=0} \\ A(m-1,1) & \mbox {if} \mbox {m>0} and \mbox {n=0} \\ A(m-1,A(m,n-1))& \mbox {if} \mbox {m>0} and \mbox {n>0} \end{cases} } for nonnegative integers m and n.
- Its value grows rapidly, even for small inputs.