Decydująca teoria asymptotycznego wzrostu

Jakie są znane granice rozstrzygalności porównania szybkości wzrostu funkcji z ? Mam na myśli rozstrzygalność pytań takich jak „Czy x x ∼ 2 ⌊ x lg ( x + 2 ) ⌋ ?” lub „Czy 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)$

Jeśli ograniczymy funkcje do wielomianów (wyrażonych w zwykły sposób), nie będzie to trudne. Zobacz także normalną formę Cantor .

Jak duże możemy uczynić klasę funkcji, zanim porównanie stanie się nierozstrzygalne? Czy możemy rozszerzyć go na funkcje używane w typowej klasie algorytmów licencjackich?

Jak wyjaśnia Joshua Grochow w komentarzach, naprawdę interesuje mnie zestaw wyrażeń, a nie same funkcje. Tak więc, na przykład, byłbym zainteresowany procedurami decyzyjnymi, które mogłyby porównywać „ ” i „ 2 ”, nawet jeśli nie mogą porównać „ ln e ” i „ n ( ln n ) - 1 ”.$1$$2$$\ln e$$n^{(\ln n)^{-1}}$

Ewentualnie powiązane pytanie: „Czy teoria granic asymptotycznych jest całkowicie aksjomatyczna?”

$\mathbb{R}$$x$$\exp$$\log|\cdot|$$f(x)^5 + f(x) = x$jest w rodzinie). Hardy wykazał, że dowolne dwie takie funkcje można porównać asymptotycznie. Nie jestem pewien, czy dowód jest algorytmiczny, ale warto to sprawdzić.

Boshernitzan rozszerzył tę klasę jeszcze bardziej i bez wątpienia istnieją inne prace na ten temat.