How Chemistry Computes: Language Recognition by Non-Biochemical Chemical Automata. From Finite Automata to Turing Machines

Every problem in computing can be cast as decision problems of whether strings are in a language or not. Computations and language recognition are carried out by three classes of automata, the most complex of which is the Turing machine. Living systems compute using biochemistry; in the artificial, computation today is mostly electronic. Thinking of chemical reactions as molecular recognition machines, and without using biochemistry, we realize one automaton in each class by means of one-pot, table top chemical reactors: from the simplest, Finite automata, to the most complex, Turing machines. Language acceptance/rejection criteria by automata can be formulated using energy considerations. Our Turing machine uses the Belousov-Zhabotinsky chemical reaction and checks the same symbol in an Avogadro′s number of processors. Our findings have implications for chemical and general computing, artificial intelligence, bioengineering, the study of the origin and presence of life on other planets, and for artificial biology.