Historical Remarks to the concept 'Automaton'

Short overviews to the history of the concept 'automaton' can be found in Perrin 1992 [227], Lakovic et al. 1999 [181], and Yu 1997 [300]. Additionally one has to consult the general literatur about computation and the turing machines like Davis 1958 [74], Davis 1965 [75], Hodges 1983 [133], Kneal & Kneal 1986 [156], as well as Gandy 1988 [113],

According to these authors we have to root the modern mathematical concept of an automaton back to Turing 1936/7 to his foundational paper about a computational concept ([274]), which has -according to Hodges 1988 [134]- been named by Church 1937 in his review of Turing's paper as Turing Machine(cf. [59]).

As far as we know is the Turing Machine concept until today the most general computing device; all other formalisms having claimed to represent a universal computing function could be shown to be equivalent with the Turing Machine concept.

But as we have learned since the appearance of the Turing Machine concept there are weaker concepts like the turing machine, which are also representing a computing device and showing great practical potentials.

Historically an important step seems to be the investigations of McCulloch and Pitts 1943 [195] to reconstruct the computing properties of neural networks inspired by the work of A.M.Turing. But they are not yet talking about a finite automaton. This is later done in a paper by Kleene 1956 [152](based on Kleene 1951 [154]), where he analyses the paper of McCulloch and Pitts from 1943 and transforms there neuronal representations in a more abstract concept called Deterministic Finite Automaton, DFA. He introduces already the concept of Regular Expressions and proofes that a finite automaton can accept exactly the set of regular expressions.

Further generalizations of the concept of a finite automaton can be found in Mealy 1955 [197] -this version of an automaton is later been called Mealy Automaton- and in Moore 1956 [205] -this version of an automaton is later been called Moore Automaton-.

An important milestone seems then to be the awarded paper from Rabin and Scott 1959 [240] in which they introduced the concept of a Nondeterministic Finite Automaton, NFA, showed a more clearer subordination of the finite automata to the turing machine, where they showed the equivalence of DFA and NFA, and where they introduced the concept of a two-way deterministic finite automaton, 2DFA.

Since then the development and the usage of the concept of finite automata has become more and more specialized in many directions (cf. Yu 1997 [300] for an overview) and has steadily gained importance.