git.iko.soy/urbit.org
on f3ca521 help sign in
urbit.org/tutorials/hoon-tutorial/ackermann.md
32 lines 1.3 kB history raw
1+++
2title = "1.6.1 Walkthrough: Ackermann Function"
3weight = 14
4template = "doc.html"
5aliases = ["docs/learn/hoon/hoon-tutorial/ackermann/"]
6+++
8The Ackermann function is one of the earliest examples of a function that is both totally computable -- meaning that it can be solved -- and not primitively recursive -- meaning it can not be rewritten in an iterative fashion.
10In this lesson, we will write a gate that computes the [Ackermann function](https://en.wikipedia.org/wiki/Ackermann_function)
12``` hoon
13|= [m=@ n=@]
14?: =(m 0) +(n)
15?: =(n 0) $(m (dec m), n 1)
16$(m (dec m), n $(n (dec n)))
17```
19With the first line, `|= [m=@ n=@]`, we create a gate that takes two arguments, `m` and `n`, both of the `@` type.
23There are three cases.
25First, if `m` is zero, return the increment of `n`.
26Second, if `n` is zero, decrement `m`, set `n` to 1 and recurse.
27Else, decrement `m` and set `n` to be the value of the Ackermann function with `n` and the decrement of `n` as arguments.
29This 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 `m` is `4` and `n` is `2` is an integer with 19,729 digits.
32### [Next Up: Reading -- Arms and Cores](../arms-and-cores)