Rational functions with a common iterate Let $f$ and $g$ be two rational functions. To avoid trivialities, we suppose that their degrees are
at least $2$. We say that they have a common iterate if $f^m=g^n$ for some positive integers $m,n$,
where $f^m$ stands for the $m$-th iterate.

1. Can one describe/classify all such pairs?

This is probably very hard, and perhaps there exists no simple answer. But here is a simpler question:

2. Is there an algorithm which finds out whether two rational functions have a common iterate or not ?

I mean, I give you  two rational functions, say with integer coefficients, and you tell me whether they have a common iterate or not. Perhaps using a super-computer...
Motivation. J. F. Ritt,
(Permutable rational functions.
Trans. Amer. Math. Soc. 25 (1923), no. 3, 399-448)
gave a complete classification/description of all commuting pairs of
rational functions (that is $f(g)=g(f)$)... except when they have
a common iterate. I gave a completely different proof of Ritt's theorem,
but again it does not apply to the case when $f$ and $g$ have a common
iterate (MR1027462).
Polynomial pairs (commuting, or with a common iterate) are completely
described in
MR1501149
Ritt, J. F.
On the iteration of rational functions.
Trans. Amer. Math. Soc. 21 (1920), no. 3, 348-356, in the very end of this paper.
What is the exact relation between permutable pairs and pairs with a common iterate ?

3. If two functions
  have a common iterate, must they commute?

Or perhaps they must, but with explicitly listed exceptions?
A positive answer to this will solve problem 2 above.
See also my "answer" to 
on common fixed points of commuting polynomials (and rational functions) for an additional motivation.
EDIT. And one more question:

4. Can one describe commuting functions that have a common iterate?

This would complete Ritt's description of commuting functions.
 A: I am replacing my previous incorrect answer by this one. I just learned about a recent preprint by Hexi Ye, 
http://arxiv.org/pdf/1211.4303.pdf
Among other things, he  proves, for general $f$ with degree $d \geq 3$, that $\mu_f=\mu_g$ implies that $f$ and $g$ share an iterate  (the converse is well known). The symbol $\mu_f$ denotes the unique $f$-invariant measure of maximal entropy for $f$ (and similarly for $g$). He also analyzes generic maps of degree $2$. The proof involves some holomorphic maps from $t \in \mathbb{C}$ to $f_t \in \rm{Rat}_d$, the set of rational functions of degree $d$  (not semigroups, which you point out to be impossible). As far as I can tell at the first glance, he does not seem to address the commutativity question. 
A: Over ${\bf C}$, An easy counterexample to question 3 is
$f(x) = x^2$, $g(x) = cx^2$ where $c$ is a nontrivial cube root of unity.
Then $f(f(x)) = g(g(x)) = x^4$ but $f$ and $g$ do not commute.
There are similar examples for higher iterates.
[Added later] A more exotic construction yields further examples,
some defined over ${\bf Q}$, such as the degree-4 pair
$$
f(y) = \frac{y^4+18y^2-47}{8y^3}, \phantom{\infty}
g(y) = \frac{f-3}{f+1} = \frac{y^4-24y^3+18y^2-27}{y^4+8y^3+18y^2-27}
$$
with $f \circ f = g \circ g$ but $f \circ g \neq g \circ f$.
This is a "Lattès map" associated to the elliptic curve
$E: y^2 = x^3 + 1$: the function $f$ comes from the doubling map
$P \mapsto 2P$, and $g$ comes from $P \mapsto 2P+T$ where $T$ is the
3-torsion point $(0,1)$ (as the $(f,g)=(x^2,cx^2)$ example
does on the multiplicative group).  This elliptic curve yields
examples of $f \circ f = g \circ g$ and $f \circ g \neq g \circ f$
with any degree $m^2+mn+n^2$ as long as that's not a multiple of 3,
with $f,g \in {\bf Q}(y)$ if $n=0$.  Other elliptic curves with complex
multiplication yield further examples using the $x$-coordinate
rather than the $y$-coordinate, e.g. 
$f(x) = -x(x^4+6x^2-3)^2 / (3x^4-6x^2-1)^2$ and $g = (f-1)/(f+1)$
from tripling on $y^2=x^3-x$.
A: Regarding the second question the algorithm is as follows:


*

*Find the flows (superfunctions) of the both functions in closed form

*See if they coincide at integer points.
For example, $f(x)=x^2$, $g(x)=x^4$.
The flows will be respectively, $C^{2^x}$, $C^{4^x}$.
Now we solve
$$C^{2^x} = C^{4^y}$$
and find $y=x/2$
This equation obviously has infinitely many integer solutions.
A more complicated case is when $f(x)=\frac{x+1}{x-1}$, $g(x)=\frac{x-1}{x+1}$
In this case the flows are:
$$f^*(x)=\frac{C \cos \left(\frac{3 \pi  x}{4}\right)+\sin \left(\frac{3 \pi  x}{4}\right)}{\cos \left(\frac{3 \pi  x}{4}\right)-C \sin \left(\frac{3 \pi  x}{4}\right)}$$
$$g^*(x)=\frac{\left(\left(\sqrt{2}-1\right) C-1\right) (-1)^x+\sqrt{2} C+C+1}{\left(-C+\sqrt{2}+1\right) (-1)^x+C+\sqrt{2}-1}$$
Solving equation f*(x) = g*(y) for integer x and y gives $x=4m, y=n$
