Hyper operators in computability theory

[JmsNxn]

Recently I asked this question on MO http://mathoverflow.net/questions/261538...n-analysis

And I'm curious if anyone has encountered anything similar. As in, the main value of the hyper-operators defined for natural numbers is its computational aspect. Is there a similar idea in analysis? Can anyone give me any ideas of where to talk about these things. About how to phrase the fact that the computational complexity of \( \sqrt{2}\uparrow^n x \) grows hyper operationally with \( n \).

[tommy1729]

Recently I asked this question on MO http://mathoverflow.net/questions/261538...n-analysis

And I'm curious if anyone has encountered anything similar. As in, the main value of the hyper-operators defined for natural numbers is its computational aspect. Is there a similar idea in analysis? Can anyone give me any ideas of where to talk about these things. About how to phrase the fact that the computational complexity of \( \sqrt{2}\uparrow^n x \) grows hyper operationally with \( n \).

In the most General case computational complexity is a very hard and unsolved area of research.
For instance take euler's gamma : if irrational , the complexity is finite. But we do not know.
The fastest algorithm or even a quadratic speed algorithm for its digits is unknown.

As for your case : 

I hope you meant superexponentially INSTEAD of hyper operationally.

Second , it seems you want a fastcut for functions like exp exp and exp exp exp.

Well if the stirling Numbers or its generalisations will not help , I assume it can not be done.

Reminds me of Stephen Wolfram's irreducible complexity.

Besides the acceleration by 2 or 3 iterates at once and the alike , one could try a nonconstant iteration speedup, but that would require a superfunction or Abel function AND a fast method for THAT Abel or super.

Combinatorical methods probably reduce to the above.

Number theory seems unrelated in a noncombinatorical sense.

Fake function theory can be fast but not precise.

Contour integrals ??

Im not optimistic since i just Summarized imho the most realistic ideas.


Sorry


Regards

Tommy1729

[MphLee]

Hi James
I guess that I tried to bring something similar to the forum's attention long ago.
Try to look here
http://math.eretrandre.org/tetrationforu...hp?tid=945

In my humble opinion this seems like something really near to what you are looking for. I red often of "extension" of recursion theory(aka computability) to real valued functions and, it seems to me, it was always near topics like measure spaces but or things like descriptive set theory (that also deals with computabiliy of subset of real numbers and of their cartesian product - i. e. functions, functionals, relations and so on). Serch about Campagnolo and Moore stuff.

Also this reminds that also bo198214 seemed to pursuit something related to this, at least judging from some MO questions
note: (is interesting that the majorisation order is proven to be a well order on two subclasses defined by Skolem of E_3 (Kalmar's elementary functions ) and E_4, see here http://link.springer.com/chapter/10.1007...4_2#page-1 )

http://mathoverflow.net/questions/60264/...-functions
http://mathoverflow.net/questions/60093/...-functions

Yes, those are only hints, I tried this path some years ago... but my ignorance of basic analytical method and lack of enough time scared me away from this.
This fact is really interesting since in my opinion the real core of all this matter (ranks and friends) lies in the group or monoid structure of the collection of functions investigated and I have strong evidences of this... and to be more precise in the conjugation relation (a relaxed version in the monoid but this still makes sense). Conjugation is strictly connected to...guess what? Hom-functors of special dynamical systems-like-categories (and home functors are something that remind alot exponentiation)...

But aside form these speculations there is a subtle connection going on here between ranks, computation complexity and dimension.(*)

Back to the wild speculations... seems like the dimensions, degrees, continuity classes and alike are to the concept of rank AS their algebraic, graded, topological, differential kind of structured collection of functions are to an unknown recursion-related algebraic structure.
Also something really obvious is that the structure of ranks (linked with orders of infinity and) seems too complex to be "parametrized" by the field of real numbers or complex numbers... maybe it is the case that the structure of the ranks (the quotient of the set of functions by the same-rank-equivalence relation) forms an important new algebraic structure...

Try also these (I did not read these actually, maybe partially bot not totally understood but I hope something can be useful for you):
http://www.sciencedirect.com/science/art...4X04000408
http://math.isa.utl.pt/~mlc/phdthesis.pdf
https://www.reading.ac.uk/web/files/math..._paper.pdf
(*) http://www.personal.psu.edu/t20/papers/sdedc.pdf (Symbolic dynamics: entropy = dimension = complexity)


I apologize in advance for the mistakes, If I, or you, will spot some errors I'll edit ASAP.

[MphLee]

Some remarks

But aside form these speculations there is a subtle connection going on here between ranks, computation complexity and dimension.(*)

I didn't mean that. The paper does not talk about ranks but only about complexity, dimension and entropy.

About the analogies... I guess that it's easy to see! There is a subtle and fascinating network of analogies between all these concepts.
And if  it is not, start by what is probably the most easy-to-spot analogy. (remember that I'm not making the domains precise, I'm just trying to be suggestive)
The ackermann function and all the recursive(but not-primitive) functions that are "beyond" the \( {\mathcal E}_n \) hierarchy (finite rank) are a bit like the transcendental functions (or smooth, or analytic) that are beyond the polynomial (finite degree): in both cases we have a procedure going back "through dimensions" (differences and anti-recursion) and  in the other direction a mutivalued procedure (indefinite sum and not based-recursion/iteration) going upstairs... it is like we are generalizing this graded structure of polinomials (well behaved, commutative, familiar objects) to more exotic, non-commuative frameworks (like group of functions, monoids and so on..). 
Amazingly this can be made very precise.

[JmsNxn]

I don't have time at the moment, but I'll be sure to read all this literature you've provided! I'll get back to you on what I think when I've digested it all.

[MphLee]

ok, take your time.

Anyways I think this is only the tip of the iceberg.

About clone theory ... this is insanely curious. This is not a theory that you meet that often... at least I don't. This is the second time I hear of that and the first time was... inside an answer an MSE user gave me about compatible posets on algebraic structures.. to be more precise I had in mind the transitive closure of dynamical systems (defined by left or right translations of binary operations) ... and he came up with the fact that it is sufficient to look at the compatibility of quasiorders on monounary algebras... that are just dynamical systems where the phase space need not to be a metric space or a topological one.

Obviously I went into this because monounary algebras are the synthetic way to talk about ranks in full abstraction. There you can define connectedness, define a meet operation, talk about three kind of ranks too (finite, period, "co-rank" and rank relative to an element) and alot of other interesting notions form a purely algebraic point of view that is more fundamental  than the topological features of dynamical systems. (fixed points, cyclic/periodical points, the lattice of the iterations are all algebraic in nature. look)

And Clone theory seems so unrelated to all of this that I do not know well what to think.