Sudan function is a fast growing function discovered by Gabriel Sudan. It is similar to the Ackermann function (but less well-known) and formally defined as follows:
\(F_0(x,y) = x+y\)
\(F_{n+1}(x,0) = x\) (for \(n \geq 0\))
\(F_{n+1}(x,y+1) = F_n(F_{n+1}(x,y),F_{n+1}(x,y)+y+1)\) (for \(n \geq 0,y \geq 0\))
It has been proven that the function is not primitive recursive.
Values
It can be shown that \(F_1(x,y) = F_1(0,y)+2^y \times x\). Below is the table for values of \(F_2(n)\).
| y \ x | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 |
| 1 | 1 | 8 | 27 | 74 | 185 | 440 |
| 2 | 19 | 10228 | \(\approx 1.55 \times 10^{10}\) | \(\approx 5.74 \times 10^{24}\) | \(\approx 3.67 \times 10^{58}\) | \(\approx 5.08 \times 10^{135}\) |