<p>Hardy, in his classical book <em>Orders of infinity</em>, considered the class of logarithmic-exponential functions. This is a rather general class of functions, which is the minimal set of functions containing $\mathbb{R}$ and $x$, closed under addition, multiplication and division (unless it has infinitely many zeroes), closed under $\exp$ and $\log|\cdot|$ (same constraint), and closed under solution of polynomial equations (i.e. the function satisfying $f(x)^5 + f(x) = x$ is in the family). Hardy showed that any two such functions can be compared asymptotically. I'm not sure if the proof is algorithmic, but it is worth checking.</p>

<p><a href="http://download.springer.com/static/pdf/792/art%253A10.1007%252FBF02803337.pdf?auth66=1390889756_dd93b903f7ce69aec8a4831dcf137730&amp;ext=.pdf">Boshernitzan</a> extended this class even further, and doubtlessly there is other work on the subject.</p>

CC BY-SA 3.0
2014-01-30T07:33:58.030Z
John R. Shackell's book "Symbolic Asymptotics" claim (section 5.1, page 91), that the first algorithm for this problem was from [Dahn and Goring's 1986 paper, "Notes on exponential-logarithmic terms"](http://matwbn.icm.edu.pl/ksiazki/fm/fm127/fm12714.pdf). Dominik Gruntz's 1996 dissertation, ["On Computing Limits in a Symbolic Manipulation System"](ftp://ftp.inf.ethz.ch/doc/dissertations/th11432.ps.gz) also contains an algorithm for this problem and compares various methods.
jbapple
CC BY-SA 3.0
2014-01-30T07:50:01.183Z
However, these all rely on an oracle for solving the zero-equivalence problem, which is undecidable in general.
jbapple
CC BY-SA 3.0
2014-01-26T06:24:03.897Z
2014-01-26T06:24:03.897Z
Yuval Filmus
<p>What are the known limits of the decidability of the comparison of growth rate of functions from $\mathbb{N} \to \mathbb{N}$? I am here thinking of the decidability of questions like "Is $x^x \sim 2^{\lfloor x \lg (x+2) \rfloor}$?" or "Is $2^{\lg^* x} \in O(\lg \lg x)$?".</p>

<p>If we restrict the functions to be polynomials (expressed in the usual manner), then this isn't hard. See also <a href="https://en.wikipedia.org/wiki/Ordinal_arithmetic#Cantor_normal_form">Cantor normal form</a>.</p>

<p>How large can we make the class of functions before comparison becomes undecidable? Can we extend it to the functions used in a typical undergraduate algorithms class?</p>

<p>As Joshua Grochow explains in the comments, I'm interested really in the set of expressions, not the functions themselves. So, for instance, I'd be interested in decision procedures that could compare "$1$" and "$2$", even if they can't compare "$\ln e$" and "$n^{(\ln n)^{-1}}$".</p>

<p>Possibly related question: <a href="https://cstheory.stackexchange.com/questions/14045/is-the-theory-of-asymptotic-bounds-finitely-axiomatizable">"Is the theory of asymptotic bounds finitely axiomatizable?"</a></p>

CC BY-SA 3.0
2014-01-26T04:10:22.007Z
Interesting question! I think one part should be changed a bit though. I don't think the question should be how large the class of functions is, but rather *how the functions are expressed*. That is, if you're given two polynomial-time Turing machines as input, telling which one has a larger running time is undecidable (despite the fact that both have polynomial running times)... If those functions were instead expressed as, say, explicit polynomials (write out the whole poly w/ coefficients) then it's easy to compare.
Joshua Grochow
CC BY-SA 3.0
2014-01-26T04:24:20.037Z
Good point. Do you have any suggestions about how to word that?
jbapple
CC BY-SA 3.0
2014-01-26T04:53:36.577Z
I guess it depends what you're interested in. It might be natural to ask for functions expressed as formula involving various operations, and then the question is what sets of operations make it decidable/undecidable. e.g. ops would include +, times, divide, -, nth roots, exp, log, composition, log^*, etc. (If you leave out log^*, the preceding list gives you all elementary functions.)
Joshua Grochow
<decidability><asymptotics>
Decidable theory of asymptotic growth
jbapple
# Decidable theory of asymptotic growth

(Asked by: username_0 on 2014-01-26)

What are the known limits of the decidability of the comparison of growth rate of functions from $\mathbb{N} \to \mathbb{N}$? I am here thinking of the decidability of questions like "Is $x^x \sim 2^{\lfloor x \lg (x+2) \rfloor}$?" or "Is $2^{\lg^\* x} \in O(\lg \lg x)$?".

If we restrict the functions to be polynomials (expressed in the usual manner), then this isn't hard. See also [Cantor normal form](https://en.wikipedia.org/wiki/Ordinal_arithmetic#Cantor_normal_form).

How large can we make the class of functions before comparison becomes undecidable? Can we extend it to the functions used in a typical undergraduate algorithms class?

As username_1 explains in the comments, I'm interested really in the set of expressions, not the functions themselves. So, for instance, I'd be interested in decision procedures that could compare "$1$" and "$2$", even if they can't compare "$\ln e$" and "$n^{(\ln n)^{-1}}$".

Possibly related question: ["Is the theory of asymptotic bounds finitely axiomatizable?"](https://cstheory.stackexchange.com/questions/14045/is-the-theory-of-asymptotic-bounds-finitely-axiomatizable)

**Tags:** decidability, asymptotics

> **Comments:**
> **username_1**: Interesting question! I think one part should be changed a bit though. I don't think the question should be how large the class of functions is, but rather *how the functions are expressed*. That is, if you're given two polynomial-time Turing machines as input, telling which one has a larger running time is undecidable (despite the fact that both have polynomial running times)... If those functions were instead expressed as, say, explicit polynomials (write out the whole poly w/ coefficients) then it's easy to compare.  
> **username_0**: Good point. Do you have any suggestions about how to word that?  
> **username_1**: I guess it depends what you're interested in. It might be natural to ask for functions expressed as formula involving various operations, and then the question is what sets of operations make it decidable/undecidable. e.g. ops would include +, times, divide, -, nth roots, exp, log, composition, log^*, etc. (If you leave out log^*, the preceding list gives you all elementary functions.)  

---

## 1 answers

### Answer by username_2 on 2014-01-26. Score: 9 | Accepted answer

Hardy, in his classical book *Orders of infinity*, considered the class of logarithmic-exponential functions. This is a rather general class of functions, which is the minimal set of functions containing $\mathbb{R}$ and $x$, closed under addition, multiplication and division (unless it has infinitely many zeroes), closed under $\exp$ and $\log|\cdot|$ (same constraint), and closed under solution of polynomial equations (i.e. the function satisfying $f(x)^5 + f(x) = x$ is in the family). Hardy showed that any two such functions can be compared asymptotically. I'm not sure if the proof is algorithmic, but it is worth checking.

[Boshernitzan](http://download.springer.com/static/pdf/792/art%253A10.1007%252FBF02803337.pdf?auth66=1390889756_dd93b903f7ce69aec8a4831dcf137730&ext=.pdf) extended this class even further, and doubtlessly there is other work on the subject.

> **Comments:**
> **username_0**: John R. Shackell's book "Symbolic Asymptotics" claim (section 5.1, page 91), that the first algorithm for this problem was from [Dahn and Goring's 1986 paper, "Notes on exponential-logarithmic terms"](http://matwbn.icm.edu.pl/ksiazki/fm/fm127/fm12714.pdf). Dominik Gruntz's 1996 dissertation, ["On Computing Limits in a Symbolic Manipulation System"](ftp://ftp.inf.ethz.ch/doc/dissertations/th11432.ps.gz) also contains an algorithm for this problem and compares various methods.  
> **username_0**: However, these all rely on an oracle for solving the zero-equivalence problem, which is undecidable in general.  

---

