Algorithm for least distance of powers of integers From Michailescu's theorem (Catalan's conjecture) we have that the only $a,b,m,n \in \mathcal{Z}^{+}$ with $m,n>1$ such that $a^{m} - b^{n} = 1$ are: $a=3$, $b=2$, $m=2$, $n=3$. 
1) Is there an algorithm which, for any $a,b \in \mathcal{Z}^{+}$ finds the minimum of $|a^{m} - b^{n}|$ $\forall m,n \in \mathcal{Z}^{+}$ (with $m,n>1$ )?
2) Do we know for how many different values of $m,n$ this minimum distance can be achieved?
3) If we do not have such an algorithm, do we know if this problem is decidable?
 A: When a, b are given, I presume you can get a lower bound for |a^m - b^n| by using lower bounds for linear forms in logarithms (applied to the form m log a - n log b.)  This reduces you to finitely many possibilities for the mininum of |a^m - b^n|.  For each possibility c, the equation a^m - b^n = c is an S-unit equation (where S contains all primes dividing a and b) and this again you can solve effectively by transcendental means.
The constants here might end up being pretty large.  For the particular problem you ask about, there is a nice theorem of Mike Bennett which asserts there is at most one pair (m,n) such that a^m - b^n is small.  Earlier work of Scott and Styer cited in Bennett's paper also seems relevant to your question.
A: I'd be curious to know how often the closest pair has $\min(m,n)>2$. Bennett shows that $|a^m-b^n|<\frac{\max(\sqrt{a^m},\sqrt{b^n})}{4}$ happens at most once. However this might not happen for most pairs $a,b$ and even when this happens, it might not be a min. (And it seems rare for it to happen with $\min(m,n)>1$.) A rather spectacular (to my mind) case is $13^3-3^7=10$. The first few convergents of the continued fraction for the ratio of the logs are $1/2,2/5,3/7,239/558$ This shows that 3/7 is an extremely good approximation (of course). But the closest pair is $13^1-3^2=4$.
later I looked for instances of $|a^m-b^n|<b$ with $2 \le a \le 99$ $n\ge 3$ and $m<200$ (also $a<b$ and neither a nor b a power of a smaller integer ). The only instances are $2^7-5^3=3$ and $13^3-3^7=10$. Both of these happen to have $|a^m-b^n|=b-a$
