  Complexity has been a recurrent research topic in cellular automata because
they represent systems where complex behaviors emerge from simple local
interactions. A significant amount of previous research has been conducted
proposing instances of complex cellular automata; however, most of the proposed
methods are based on a careful search or a meticulous construction of evolution
rules.
  This paper presents the emergence of complex behaviors based on reversible
cellular automata. In particular, this paper shows that reversible cellular
automata represent an adequate framework to obtain complex behaviors adding
only new random states.
  Experimental results show that complexity can be obtained from reversible
cellular automata appending a proportion of about two times more states at
random than the original number of states in the reversible automaton. Thus, it
is possible to obtain complex cellular automata with dozens of states.
Complexity appears to be commonly obtained from reversible cellular automata,
and using other operations such as permutations of states or row and column
permutations in the evolution rule. The relevance of this paper is to present
that reversibility can be a useful structure to implement complex behaviors in
cellular automata.
