  This paper introduces and studies a new model of computation called an
Alternating Automatic Register Machine (AARM). An AARM possesses the basic
features of a conventional register machine and an alternating Turing machine,
but can carry out computations using bounded automatic relations in a single
step. One finding is that an AARM can recognise some NP-complete problems,
including SAT (using a particular coding), in $\log^* n + O(1)$ steps. On the
other hand, if all problems in P can be solved by an AARM in $O(\log^*n)$
rounds, then $\text{P} \subset \text{PSPACE}$.
  Furthermore, we study an even more computationally powerful machine, called a
Polynomial-Size Padded Alternating Automatic Register Machine (PAARM), which
allows the input to be padded with a polynomial-size string. It is shown that
the polynomial hierarchy can be characterised as the languages that are
recognised by a PAARM in $\log^*n + O(1)$ steps. These results illustrate the
power of alternation when combined with computations involving automatic
relations, and uncover a finer gradation between known complexity classes.
