"Evolutionary automata", a generalization of "Evolutionary Turing machines", have been introduced in order to investigate more precisely properties of biological and evolutionary computation. In particular, they allow to obtain new results on expressiveness of evolutionary computation. This confirms the initial result about undecidability of natural evolution and evolutionary algorithms and processes. "Evolutionary finite automata", the simplest subclass of Evolutionary automata working in "terminal mode" can accept arbitrary languages over a given alphabet, including non-recursively enumerable (e.g., diagonalization language) and recursively enumerable but not recursive languages (e.g., language of the universal Turing machine).