Difference between revisions of "Manuals/calci/ACKERMANN"

Latest revision as of 20:10, 14 February 2019

ACKERMANN(m,n)

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.
The two-argument Ackermann–Péter function, is defined as follows:

$A(m,n)={\begin{cases}n+1{\mbox{if}}m=0\\A(m-1,1)&{\mbox{if}}m>0andn=0\\A(m-1,A(m,n-1))&{\mbox{if}}m>0andn>0\end{cases}}$ \\

for nonnegative integers m and n.

@@ Line 6: / Line 6: @@
 *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:
+*The two-argument Ackermann–Péter function, is defined as follows:
 <math>A(m,n) = \begin{cases} n+1 \mbox {if} m=0 \\
 A(m-1,1) & \mbox {if}  m>0 and  n=0 \\
 A(m-1,A(m,n-1))& \mbox {if} m>0 and n>0
-\end{cases} </math>
+\end{cases} </math>\\
-for nonnegative integers m and n.
+ for nonnegative integers m and n.
 *Its value grows rapidly, even for small inputs.
+==Example==
+==Related Videos==
+{{#ev:youtube|v=CUbDmWIFYzo|280|center|Ackermann}}
+==See Also==
+*[[Z_API_Functions | List of Main Z Functions]]
+*[[ Z3 |   Z3 home ]]
+==References==
+[https://en.wikipedia.org/wiki/Ackermann_function Ackermann Function]
+*[[Z_API_Functions | List of Main Z Functions]]
+*[[ Z3 |   Z3 home ]]