Duenas-Diez, Marta and Juan Perez-Mercader
Computation—defined as the pathway for information to be input, to be processed mechanically, and to be output in a useful way (Evans 2011)— takes place not only in the myriad of electronic devices we use daily but also in living systems. Life carries out computations mostly by using chemical support: inputs are chemical substances, the mechanical processing occurs via chemical reaction mechanisms, and the result is chemical as well. Machines carrying out computations are typically referred to as automata (Hopcroft, Motwani, and Ullman 2006); hence, to a large extent, living systems can be viewed as chemical automata (Bray 2009). Classic automata are arranged hierarchically from simplest to most powerful (Hopcroft, Motwani, and Ullman 2006): finite automata, then push-down automata, and, at the top of the hierarchy, Turing machines (Turing 1936).