15
$\begingroup$

Ackermann's function is defined over integers $x$, $y$, $A(x,y)$, with conditions for when $x=0$ or $y=0$, and otherwise uses recursive definitions involving arguments $x-1$ and $y-1$.

Is there a natural generalizations of $A(x,y)$ for $x,y \in \mathbb{R}$?

Perhaps this is well-known to the cognoscenti. I'd appreciate a pointer.

$\endgroup$
5
  • 1
    $\begingroup$ +1 For example, is there a continuous function on the non-negative real quarter-plane satisfying the Ackermann recursion? $\endgroup$ Nov 3 '13 at 2:29
  • 2
    $\begingroup$ In particular, one part of the Ackerman function is essentially "tetration", x^x^x...^x up to level y, so any such generalization would solve the problem of extending tetration to real y. Generally, such discussion should be referred to the tetration web sites, and not done here in MO. $\endgroup$ Nov 3 '13 at 14:01
  • 2
    $\begingroup$ I do not quite get the logic of your argument $\endgroup$ Nov 3 '13 at 16:16
  • 1
    $\begingroup$ @GeraldEdgar What are "the tetration web sites"? $\endgroup$ Jul 23 at 17:35
  • $\begingroup$ @AlexKruckman ... see references at en.wikipedia.org/wiki/Tetration $\endgroup$ Jul 23 at 19:07
10
$\begingroup$

It seems that we may extend the Ackermann function to the non-negative real plane with a continuous real-valued function obeying the Ackermann recursion.

Specifically, consider the Ackermann function defined on the Wikipedia page to which you link, which is equivalent to the following: $$A(m,n)=\begin{cases} n+1 &\text{ if }m=0\\ A(m-1,1) &\text{ if }m\geq 1\text{ and }n=0\\ A(m-1,A(m,n-1)) &\text{ if }m\geq 1\text{ and }n\geq 1 \end{cases}$$ Let us simply define the real-valued $A(m,n)$ on the unit square, that is, for $0\leq m,n\leq 1$, in such a way that it has the right values at the four corners and is continuous and increasing in each coordinate on the square. Now we simply extend the domain of our function by applying the recursive rule, which reduces any value to the values appearing inside an already defined box (and we must define $A(m,n)$ when $0\leq n\leq 1$ so as to continuously extend what is required when $n=0$ and $n=1$). That is, we define the function $A(m,n)$ integer-strip-by-integer-strip by recursion on the greatest integer in $m$, and within any integer strip by recursion on greatest integer in $n$. The value of the function inside any box determined by the integer lattice is the composition of continuous functions, and agrees with the values of the ordinary Ackermann function on the integer points themselves. So the result is a continuous function obeying the Ackermann recursion.

$\endgroup$
10
  • 1
    $\begingroup$ I'm curious about how nice this (or any related) function is. In particular, can we make it analytic? (That is, is there an analytic function whose behavior on the non-negative real numbers is described above?) That might be obvious, but it's late and I'm not seeing it. $\endgroup$ Nov 3 '13 at 4:45
  • $\begingroup$ It seems one could indeed make it very smooth... $\endgroup$ Nov 3 '13 at 4:49
  • 6
    $\begingroup$ Is there some kind of convexity condition we could apply, like in the Gamma function? $\endgroup$
    – Will Sawin
    Nov 3 '13 at 5:23
  • 1
    $\begingroup$ @alex.peter Don't I address your concern in my sentence asserting, "we must define $A(m,n)$ when $0\leq n\leq 1$ so as to continuously extend what is required when $n=0$ and $n=1$"? It seems we are a little free in those initial boxes in each row. (And I don't understand your concern about linearity, since clearly the function has little to do with linearity.) $\endgroup$ Jul 24 at 17:05
  • 2
    $\begingroup$ I was trying to convey the idea that there will be many continuous extensions to the reals that obey the Ackermann recursion. Yes, we could pick a specific one, but it seemed more insightful to me to point out that there is some flexibility remaining beyond the recursion, and pointing out exactly where that flexibility lies. $\endgroup$ Jul 24 at 17:15
2
$\begingroup$

$$A(x,y)=\begin{cases} x+y+1 & \text{ if } 0 \leq x \lt 1 \\ A(x-1,y+1) &\text{ if } 0 \leq y \lt 1, x \geq 1 \\ A(x-1,A(x,y-1)) &\text{ otherwise } \end{cases} $$

Very nice and smooth and gives no headache in any particular sense.

If you look at the definition the only missing element is $A(p,q), 0 \leq p<1$ the rest is purely recursive and does not depend on the nature of the number. Notice that Akerman function is very complicated but still a counting function since the only non recursive rule is $A(0,n)=n+1$, so a linear extension is the most natural one.

Notice it is very naturally $A(\frac{1}{2},\frac{1}{2})=A(0,1)=2$

$\endgroup$
2
$\begingroup$

In order to obtain a valid and consistent extension all we need is to define how we calculate one fractional operation for example $H_{\frac{3}{2}}(x,y)$ which is something between addition and multiplication. So let us try to extend one work that says that we can use arithmetic-geometric mean and obtain such consistent extension. First thing first.

Notice that Ackermann function is directly related to hyperoperations.

$$A(m,n) = \begin{cases} 0[m]n & m=0 \\ 2[m](n+3)-3 & m>0 \\ \end{cases}$$

So let us repeat a more or less standard notation $$H_n(a,b)=a[n]b$$ $$H_0(a,b)=b+1$$ $$H_1(a,b)=a+b$$ $$H_2(a,b)=ab$$ $$H_3(a,b)=a^b$$

$$H_n(a,b)=a[n]b=a[n-1](a[n](b-1))$$

According to https://www.hindawi.com/journals/mpe/2016/4356371/ we can define $H_{\frac{3}{2}}$ using arithmetic-geometric mean, $M(x,y)$, and its inverse and one constant that we can calculate since for all hyperfunctions we know that

$$H_n(2,2)=4$$

because $2+2=4$ and $H_n(2,2)=2[n]2=2[n-1](2[n]1)=2[n-1]2$

(The author is arguing that the resulting $H_{\frac{3}{2}}$ coming from AG mean corresponds to physical process, where the analysis very likely came from, and polynomial interpolation as well.)

So it is $$H_{\frac{3}{2}}(x,y)=M^{(-1)}(M(x,y),\epsilon_{\frac{3}{2}})$$

$$\epsilon_{\frac{3}{2}}=M^{(-1)}(2,4)$$

Now that we have $H_{\frac{3}{2}}(x,y)$ we can obtain integer evaluations for $H_{\frac{5}{2}}(x,n)$ simply

$$H_{\frac{5}{2}}(x,n)=H_{\frac{3}{2}}(x,H_{\frac{3}{2}}(x,...\text{n times}))$$

The same as what we have with other operations $x \cdot n = x+x+...\text{n times}$

Now that we have integer $H_{\frac{5}{2}}(x,n)$ and $H_{\frac{5}{2}}(x,n+1)$ we can find the middle point. Notice for multiplication and exponentiation this is how we find value in the middle

$$\frac{xn+x(n+1)}{2}$$

$$\sqrt[2]{x^n x^{n+1}}$$

So $H_{\frac{5}{2}}(x,n+\frac{1}{2})$ is the solution of

$$H_{\frac{3}{2}}(x,2)=H_{\frac{3}{2}}(H_{\frac{5}{2}}(x,n),H_{\frac{5}{2}}(x,n+1))$$

And the same for whatever else middle integer we want.

Once we have $H_{n+\frac1{2}}$ we use the same division procedure to obtain $H_{n+\frac{1}{4}}$ and $H_{n+\frac{3}{4}}$ and so on and we are done. Once we have all rational fractional parts, we can extend it to real numbers even though we cannot express it in some closed form.

We can easily extend this down to $H_{\frac{1}{2}}$ using $x[1+r]y=x[r](x[1+r](y-1)), 0<r<1$ (Solve $x[1+r](z-1)=y$ and then $x[r]y=x[r+1]z$)

For the second argument $y$ in $H_n(x,y)$ (which is $n$ in $A(m,n)$) all operations: addition multiplication... naturally extend to real numbers, so there is nothing to add to that end.

Finally for $r,s \geq 0$ reals, we have

$$A(r,s) = \begin{cases} 0[r]s & r=0 \\ 2[r](s+3)-3 & r>0 \\ \end{cases}$$

where $x[r]y=H_{r}(x,y)$ is an extension over reals obtained by the above procedure using the n/n+1 hyper-mean.

Essentially this procedure is the same if we decide to use some another average operation between addition and multiplication. All comes to define just that and the rest of the construction is all the same.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.