My most prevalent interest in mathematics has always been hyper-operators. I first learned about them when I was in highschool, and quite frankly, they amazed and dazzled me. For those who've yet to hear of hyper-operators, Wikipedia is a good place to start. This question strictly concerns hyper-operators, a more offbeat area of mathematics. I'd like to think this question is a soft question, as it's rather open ended. I'm more interested in a kind of discussion, than asking for a yes or no, or a proof. References are greatly welcomed though! Anyone who might have seen something similar, and a reference to said thing would be outstanding!
To begin, let's talk shop about Hyper-operators. Essentially we define a sequence of binary operators on $\mathbb{N}$ starting with
$$a \uparrow^0 b = a \cdot b$$ $$a \uparrow^n 1 = a$$
$$a \uparrow^{n+1} b = a \; \underset{b \text{ times}}{ \underbrace{\uparrow^n a \cdots \uparrow^n a}}$$
This gives the recursive relationship $a \uparrow^n(a \uparrow^{n+1} b) = a \uparrow^{n+1}(b+1)$.
The initial motivation for their construction was a natural way to extend the three main operators of mathematics: addition, multiplication and exponentiation. One defines addition initially $$a + b = a \; \underset{b \text{ times}}{\underbrace{+ 1 \cdots +1}}$$ and then defines multiplication by $$a \cdot b = a \; \underset{b-1 \text{ times}}{\underbrace{ + a \cdots + a}} $$ and then defines exponentiation by $$a^b = a \; \underset{b-1 \text{ times}}{\underbrace{\cdot a \ldots \cdot a}}$$ where it's only natural to continue said chain by making $^b a = a^{a^{...\text{$b$ times}...^a}}$. So on and so forth ad infinitum.
These sequence of operators were used to construct the first ever non-primitive recursive function. This is aptly, Ackermann's function $F(n) = a \uparrow^n b$--which takes off faster than The Starship Enterprise at warp speed.
Because of this ungodly growth rate, there is a nice theorem on Primitive recursive functions which drops out. It is described by the Grzegorczyk hierarchy. It essentially says that primitive recursive functions can be partitioned by their growth rate.
Essentially if $f(x):\mathbb{N} \to \mathbb{N}$ is primitive recursive, there exists $N$ such that $f(x) = o(2 \uparrow^N x)$. In fact, the Grzegorczyk hierarchy, does one better, and partitions all primitive recursive functions just by their growth rate. So for instance
$$x+1, x+2, x+3,...\in E_1$$ $$2x,3x,...\in E_2$$ $$x^2, 3x^4,...\in E_3$$ $$2^x,3^{x^2}... \in E_4$$
so on and so forth. Where, a nice way to characterize it is, $f \in E_n$ if $f$ is primitive recursive and $f(x) = o(2 \uparrow^{n-2} x)$.
Now what I'm interested in is a similar idea in analysis and computability theory in analysis. Now I only really have a working knowledge of computability theory, and when adding analysis I'm somewhat of a novice, so excuse me if this sounds a bit like a naive question. Can we partition analytic functions by the time it takes to compute them? So instead of growth rate, computational rate would be the key factor.
As a key example of what I mean, and the best way to describe what I mean, let's look at hyper-operators in analysis! Let's use $\sqrt{2}$ because it's such a nice number and define $\sqrt{2} \uparrow^{-1} x = \sqrt{2} + x$ (excuse the nasty index, it's Knuth's convention).
We can do something cool by a nice inductive process. Firstly
$$\sqrt{2} \uparrow^{0} x = \sum_{n=0}^\infty \dbinom{x}{n}\sum_{m=0}^n(-1)^{n-m}\dbinom{n}{m}\sqrt{2}\uparrow^{-1}\sqrt{2}\uparrow^{-1}...\text{$m$ times}...\uparrow^{-1} \sqrt{2}$$ $$\sqrt{2} \uparrow^{0} x = \sum_{n=0}^\infty \dbinom{x}{n}\sum_{m=0}^n(-1)^{n-m}\dbinom{n}{m}\sqrt{2}\cdot m$$ $$\sqrt{2} \uparrow^{0} x = \sqrt{2}x$$
which satisfies $\sqrt{2}\uparrow^{-1}(\sqrt{2} \uparrow^{0} x)= \sqrt{2}\uparrow^{0}(x+1)$
Now let us repeat this process
$$\sqrt{2} \uparrow^{1} x = \sum_{n=0}^\infty \dbinom{x}{n}\sum_{m=0}^n(-1)^{n-m}\dbinom{n}{m}\sqrt{2}\uparrow^{0}\sqrt{2}\uparrow^{0}...\text{$m$ times}...\uparrow^{0} \sqrt{2}$$ $$\sqrt{2} \uparrow^{1} x = \sum_{n=0}^\infty \dbinom{x}{n}\sum_{m=0}^n(-1)^{n-m}\dbinom{n}{m}\sqrt{2}^m$$ $$\sqrt{2} \uparrow^{1} x = \sqrt{2}^x$$
which satisfies $\sqrt{2}\uparrow^{0}(\sqrt{2} \uparrow^{1} x)= \sqrt{2}\uparrow^{1}(x+1)$
And fantastically
$$\sqrt{2}\uparrow^2 x = \sum_{n=0}^\infty \dbinom{x}{n}\sum_{m=0}^n(-1)^{n-m}\dbinom{n}{m}\sqrt{2}\uparrow^{1}\sqrt{2}\uparrow^{1}...\text{$m$ times}...\uparrow^{1} \sqrt{2}$$ $$\sqrt{2} \uparrow^{2} x = \sum_{n=0}^\infty \dbinom{x}{n}\sum_{m=0}^n(-1)^{n-m}\dbinom{n}{m}\sqrt{2}^{\sqrt{2}^{...\text{$m$ times}...^{\sqrt{2}}}}$$
which satisfies $\sqrt{2}\uparrow^{1}(\sqrt{2} \uparrow^{2} x)= \sqrt{2}\uparrow^{2}(x+1)$. Ad infinitum this process continues, giving us a sequence that can be defined as
$$\sqrt{2} \uparrow^{0} x = \sqrt{2}x$$
$$\sqrt{2}\uparrow^{k+1} x = \sum_{n=0}^\infty \dbinom{x}{n}\sum_{m=0}^n(-1)^{n-m}\dbinom{n}{m}\sqrt{2}\uparrow^{k}\sqrt{2}\uparrow^{k}...\text{$m$ times}...\uparrow^{k} \sqrt{2}$$
And Voila! We've constructed the hyper-operators. All of this can be made completely rigorous, and is well founded.
Now what I've had difficulty expressing is the sheer computational power required to get within a decent accuracy when calculating these beasts. Going up to $\sqrt{2}\uparrow^7 x$ is confoundingly difficult, let alone trying to calculate $\sqrt{2}\uparrow^{100}x$. In my head I'm thinking these must be the most computationally heavy functions in existence!
It led me to wonder: Is there some value in the fact that these are so slowly converging? Is there some value in the fact that this is hierarchal, that $\sqrt{2} \uparrow^{n} x$ is faster to compute than $\sqrt{2} \uparrow^{n+1} x$? Or interestingly (perhaps though phrased a bit naively), does the computation time of $F(n)=\sqrt{2} \uparrow^n x$ grow like Ackermann's function grow? As in, does it take a hyperoperator amount of time to calculate hyperoperators?
Going even further, what about
$$\sum_{n=0}^\infty (\sqrt{2}\uparrow^n x) \cdot 2^{-n}$$
is this not one of the most difficult expressions on planet earth to compute (if not most). Is there some kind of importance to this? It feels that way, at least through my eyes.
Can we say something like, functions with such and such nice property can be computed faster than $\sqrt{2}\uparrow^n x$ for some $n$. Can we measure something like, let's say recursion depth (which is a way of thinking of the usual hyper-operators) by how fast they can be computed, and a function has recursion depth $n$ if it can be computed in the same length of time as $\sqrt{2}\uparrow^n x$.
Again, I'm looking for some kind of insight into this. I'm not asking anything too specific, so maybe this could be community wiki. All in all though, the biggest question I'm curious about is
Can we partition analytic functions by the amount of time it takes to compute them in a similar way that the Grzegorczyk hierarchy partitions primitive recursive functions?
References, insight, ideas, anything is greatly welcomed and appreciated.
