Values of the Sudan function

Question

I am talking about the first discovered recursive function which is not primitive recursive. I would like to know the exact values of $\ f(3,3,3), f(2,0,4), f(2,7,1), f(2,3,2)$ (where $f$ is the sudan according to this definition: https://en.wikipedia.org/wiki/Sudan_function).

Answer 1

From the definition :

$f_0(x,y)=x+y$

$f_n(x,0)=x$

$f_1(x,y+1)=2.f_1(x,y)+y+1$, so $$f_1(x,y+1)+(y+1+2)=2(f_1(x,y)+y+2)=2^{y+1}(x+2)$$

That implies $$f_1(x,y)=2^y(x+2)-y-2$$

$$f_2(x,y+1)=2^{f_2(x,y)+y+1}(f_2(x,y)+2)-(f_2(x,y)+y+1)-2$$

You can then compute using definitions :

• $f_2(7,1)=2294$
• $f_2(3,2)=5742397643169488579854258$
• $f_2(0,3)=88080360$
• $f_2(0,4)=2^{88080364}.88080362-88080364$
• $f_3(3,3)$ is completely out of reach... because $f_3(3,0)=3$ and $f_3(3,1)=f_2(3,4)$ is already out of reach...(much larger than $2^{2^{f_2(3,2)}}$)