02/15/2017, 10:10 AM
Some remarks
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.
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.
Mother Law \(\sigma^+\circ 0=\sigma \circ \sigma^+ \)
\({\rm Grp}_{\rm pt} ({\rm RK}J,G)\cong \mathbb N{\rm Set}_{\rm pt} (J, \Sigma^G)\)
