  Since the paper of Kleinberg and Kleinberg, SODA'05, where it was proven that
the preferential attachment random graph with degeneracy at least 3 does not
obey the first order 0-1 law, no general methods were developed to study
logical limit laws for recursive random graph models with arbitrary degeneracy.
Even in the (possibly) simplest case of the uniform attachment, it is still not
known whether the first order convergence law holds in this model. We prove
that the uniform attachment random graph with bounded degrees obeys the first
order convergence law. To prove the law, we describe dynamics of first order
equivalence classes of the random graph using Markov chains. The convergence
law follows from the existence of a limit distribution of the considered Markov
chain. To show the latter convergence, we use stochastic approximation
processes.
