Tetration Forum

Full Version: Hyper operators in computability theory
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
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$.
(02/07/2017, 07:59 AM)JmsNxn Wrote: [ -> ]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.

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
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
(*) 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.
Some remarks
Quote: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.
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.