Difference between revisions of "Manuals/calci/ACKERMANN"
Jump to navigation
Jump to search
(6 intermediate revisions by 2 users not shown) | |||
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. | *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. | *Its arguments are never negative and it always terminates. | ||
− | * | + | *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} 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 | 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. | *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 ]] |
Latest revision as of 20:10, 14 February 2019
ACKERMANN(m,n)
- 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.
- The two-argument Ackermann–Péter function, is defined as follows:
\\
for nonnegative integers m and n.
- Its value grows rapidly, even for small inputs.
Example
Related Videos
See Also
References