The mathematical study of abstract computing machines (especially Turing machines) and the analysis of algorithms used by such machines. A connection between automata theory and number theory was provided by Christol et al. (1980), who showed that a sequence {a_n} is generated by a p-automaton iff the formal power series with coefficients a_n is algebraic on the field of rational elements A(X)/Q(X), where A(X) and Q(X) are polynomials with coefficients in the finite field F_p.

abstract machine | cellular automaton | Turing machine