Teoría decidible del crecimiento asintótico

¿Cuáles son los límites conocidos de la capacidad de decisión de la comparación de la tasa de crecimiento de las funciones de ? Estoy aquí pensando en la capacidad de decisión de preguntas como "¿Es x x ∼ 2 ⌊ x lg ( x + 2 ) ⌋ ?" o "¿Es 2 lg ∗ x ∈ O ( lg lg x ) ?".$\mathbb{N} \to \mathbb{N}$$x^x \sim 2^{\lfloor x \lg (x+2) \rfloor}$$2^{\lg^* x} \in O(\lg \lg x)$

Si restringimos las funciones para que sean polinomios (expresados ​​de la manera habitual), entonces esto no es difícil. Ver también la forma normal de Cantor .

¿Qué tan grande podemos hacer la clase de funciones antes de que la comparación se vuelva indecidible? ¿Podemos extenderlo a las funciones utilizadas en una clase típica de algoritmos de pregrado?

Como Joshua Grochow explica en los comentarios, estoy realmente interesado en el conjunto de expresiones, no en las funciones mismas. Entonces, por ejemplo, estaría interesado en los procedimientos de decisión que podrían comparar " " y " 2 ", incluso si no pueden comparar " ln e " y " n ( ln n ) - 1 ".$1$$2$$\ln e$$n^{(\ln n)^{-1}}$

Posiblemente pregunta relacionada: "¿Es la teoría de los límites asintóticos finitamente axiomatizable?"

$\mathbb{R}$$x$$\exp$$\log|\cdot|$$f(x)^5 + f(x) = x$está en la familia). Hardy demostró que cualquiera de estas dos funciones se puede comparar asintóticamente. No estoy seguro de si la prueba es algorítmica, pero vale la pena verificarla.

Boshernitzan extendió esta clase aún más, y sin duda hay otro trabajo sobre el tema.