Write a gate to compute Ackermann's Function
|= [m=@ n=@] ?~ m +(n) ?~ n $(m (dec m), n 1) $(m (dec m), n $(n (dec n)))
Ackermann Function is one of the earliest examples of a function that is totally computable, meaning it can be solved, but is not primitive recursive, meaning it can not be rewritten in an iterative fashion.
Our gate takes two argument,
n. There are three cases.
m is zero, return the increment of
n is zero, decrement
n to 1 and recurse.
m and set
n to be the value of the Ackermann function with
n and the decrement of
n as arguments.
This is not a terribly useful function to compute but it has an interesting history in mathematics. When running this function the value grows rapidly even for very small input. The value of computing this where
2 is an integer with 19,729 digits.