FANDOM


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 Edit

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}\)

Sources Edit

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.