  The Nottingham group at 2 is the group of (formal) power series $t+a_2 t^2+
a_3 t^3+ \cdots$ in the variable $t$ with coefficients $a_i$ from the field
with two elements, where the group operation is given by composition of power
series. The depth of such a series is the largest $d\geq 1$ for which
$a_2=\dots=a_d=0$. Only a handful of power series of finite order are
explicitly known through a formula for their coefficients. We argue in this
paper that it is advantageous to describe such series in closed computational
form through automata, based on effective versions of proofs of Christol's
theorem identifying algebraic and automatic series. Up to conjugation, there
are only finitely many series $\sigma$ of order $2^n$ with fixed break sequence
(i.e. the sequence of depths of $\sigma^{\circ 2^i}$). Starting from Witt
vector or Carlitz module constructions, we give an explicit automaton-theoretic
description of: (a) representatives up to conjugation for all series of order 4
with break sequence (1,m) for m<10; (b) representatives up to conjugation for
all series of order 8 with minimal break sequence (1,3,11); and (c) an
embedding of the Klein four-group into the Nottingham group at 2. We study the
complexity of the new examples from the algebro-geometric properties of the
equations they satisfy. For this, we generalise the theory of sparseness of
power series to a four-step hierarchy of complexity, for which we give both
Galois-theoretic and combinatorial descriptions. We identify where our
different series fit into this hierarchy. We construct sparse representatives
for the conjugacy class of elements of order two and depth $2^\mu \pm 1$ $(\mu
\geq 1)$. Series with small state complexity can end up high in the hierarchy.
This is true, for example, for a new automaton we found, representing a series
of order 4 with 5 states, the minimal possible number for such a series.
