How Chemistry Computes: Language Recognition by Non-Biochemical Chemical Automata. From Finite Automata to Turing Machines
Summary: 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 art...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2019-09-01
|
| Series: | iScience |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2589004219302858 |
| _version_ | 1811267254926442496 |
|---|---|
| author | Marta Dueñas-Díez Juan Pérez-Mercader |
| author_facet | Marta Dueñas-Díez Juan Pérez-Mercader |
| author_sort | Marta Dueñas-Díez |
| collection | DOAJ |
| description | Summary: 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. : Chemistry; Chemical Reaction; Computer Science; Theory of Computation Subject Areas: Chemistry, Chemical Reaction, Computer Science, Theory of Computation |
| first_indexed | 2024-04-12T20:59:08Z |
| format | Article |
| id | doaj.art-69e4d8a20f3a4237872f6acc6e5dd416 |
| institution | Directory Open Access Journal |
| issn | 2589-0042 |
| language | English |
| last_indexed | 2024-04-12T20:59:08Z |
| publishDate | 2019-09-01 |
| publisher | Elsevier |
| record_format | Article |
| series | iScience |
| spelling | doaj.art-69e4d8a20f3a4237872f6acc6e5dd4162022-12-22T03:16:54ZengElsevieriScience2589-00422019-09-0119514526How Chemistry Computes: Language Recognition by Non-Biochemical Chemical Automata. From Finite Automata to Turing MachinesMarta Dueñas-Díez0Juan Pérez-Mercader1Repsol Technology Lab, c/ Agustín de Betancourt s/n, Móstoles, Madrid 28935, Spain; Department of Earth and Planetary Sciences, Harvard Origins of Life Initiative, Harvard University, 20 Oxford Street, Cambridge, MA 02138, USADepartment of Earth and Planetary Sciences, Harvard Origins of Life Initiative, Harvard University, 20 Oxford Street, Cambridge, MA 02138, USA; Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM 87501, USA; Corresponding authorSummary: 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. : Chemistry; Chemical Reaction; Computer Science; Theory of Computation Subject Areas: Chemistry, Chemical Reaction, Computer Science, Theory of Computationhttp://www.sciencedirect.com/science/article/pii/S2589004219302858 |
| spellingShingle | Marta Dueñas-Díez Juan Pérez-Mercader How Chemistry Computes: Language Recognition by Non-Biochemical Chemical Automata. From Finite Automata to Turing Machines iScience |
| title | How Chemistry Computes: Language Recognition by Non-Biochemical Chemical Automata. From Finite Automata to Turing Machines |
| title_full | How Chemistry Computes: Language Recognition by Non-Biochemical Chemical Automata. From Finite Automata to Turing Machines |
| title_fullStr | How Chemistry Computes: Language Recognition by Non-Biochemical Chemical Automata. From Finite Automata to Turing Machines |
| title_full_unstemmed | How Chemistry Computes: Language Recognition by Non-Biochemical Chemical Automata. From Finite Automata to Turing Machines |
| title_short | How Chemistry Computes: Language Recognition by Non-Biochemical Chemical Automata. From Finite Automata to Turing Machines |
| title_sort | how chemistry computes language recognition by non biochemical chemical automata from finite automata to turing machines |
| url | http://www.sciencedirect.com/science/article/pii/S2589004219302858 |
| work_keys_str_mv | AT martaduenasdiez howchemistrycomputeslanguagerecognitionbynonbiochemicalchemicalautomatafromfiniteautomatatoturingmachines AT juanperezmercader howchemistrycomputeslanguagerecognitionbynonbiochemicalchemicalautomatafromfiniteautomatatoturingmachines |