Teoria decente do crescimento assintótico

Quais são os limites conhecidos da decidibilidade da comparação da taxa de crescimento de funções de ? Estou aqui pensando na decidibilidade de perguntas como "Is x x ∼ 2 ⌊ x lg ( x + 2 ) ⌋ ?" ou "é 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)$

Se restringimos as funções a serem polinômios (expressos da maneira usual), isso não é difícil. Veja também o formulário normal do Cantor .

Qual é o tamanho da classe de funções antes que a comparação se torne indecidível? Podemos estendê-lo às funções usadas em uma classe típica de algoritmos de graduação?

Como Joshua Grochow explica nos comentários, estou realmente interessado no conjunto de expressões, não nas próprias funções. Assim, por exemplo, eu estaria interessado em procedimentos de decisão que pudessem comparar " " e " 2 ", mesmo que não consigam comparar " ln e " e " n ( ln n ) - 1 ".$1$$2$$\ln e$$n^{(\ln n)^{-1}}$

Pergunta possivelmente relacionada: "A teoria dos limites assintóticos é finitamente axiomatizável?"

$\mathbb{R}$$x$$\exp$$\log|\cdot|$$f(x)^5 + f(x) = x$está na família). Hardy mostrou que qualquer uma dessas duas funções pode ser comparada assintoticamente. Não tenho certeza se a prova é algorítmica, mas vale a pena conferir.

Boshernitzan estendeu essa classe ainda mais e, sem dúvida, há outros trabalhos sobre o assunto.