CiteScore: 4.9     h-index: 21

Document Type : Review Article

Authors

1 Department of Computer Engineering, Lorestan University, Khorramabad, Iran

2 Faculty of Engineering, Yasouj University, Yasouj, Iran

3 Department of Chemistry, Gachsaran Branch, Islamic Azad University, Gachsaran, Iran

Abstract

Computers that use chemical reactions for information processing could solve problems parallel and faster than conventional computers. Developing conventional computers based on Moore's law is impossible due to some system limitations. Thus, alternative technologies are emerging. Chemical computing based on BZ reactions is one of the emerging technologies. This technology is a bridge between computer science and chemistry. Highly parallel computing, and the relative ease of laboratory experiments and simulation in two-dimensional cellular automata make chemical computing a valuable tool for developing unconventional computing. This work discusses the basic principles, functions, applications, and research progress in chemical computing. This review will also highlight the applications of chemical computing, including image processing and pattern recognition, and recent research will be addressed.

Graphical Abstract

Chemical Computers and Computing Based on Chemical Reactions: Current Status and Outlook

Keywords

Introduction

Current digital computers are constructed with silicon, and conventional computing is based on the semiconductor industry. Everyone might appreciate the success of computing based upon semiconductor technology determined using Moore's law [1]. Moore's law states that the circuit power and complexity will be doubled every two years. In addition, it is easy to understand that the law projected by Moore cannot be continued indefinitely because of some system constraints (or system bottlenecks). Therefore, it motivates any researcher in this field to evaluate alternative computing techniques. Unconventional computing [2–6] is a field of research devoted to biology, physics, or chemistry, such as DNA computing, quantum computing, and chemical computing. Conventional computers are based on von Neumann architecture (which often limits the system's performance) and compute serially. In contrast, unconventional computers seem to be massively parallel [7-10].

The chemical reactions that stand behind information processing are implemented by chemical computing. In nature, biochemical processes happen in an animal brain responsible for information processing. Chemical reactions reach a stable equilibrium. In 1950 Boris Belousov, a Soviet chemist and biophysicist, found the Belousov–Zhabotinsky reaction (BZ reaction) that did not reach equilibrium [11]. This reaction became the basis of chemical computing. This emerging technology has a fascinating and rich history that prompted us to write this review, highlighting a few of its key developments. Chemical computers based on BZ reaction simulate logic gates and circuits, execute image processing and pattern recognition, language recognition, solve optimization problems and control mechanical devices as a liquid brain [12-22].

In this research study, we focused on chemical computing, its applications and the latest studies conducted in this field. In the following, the BZ reaction will be discussed, which may assist the reader in better understanding other sections.  

BZ Reaction

In 1950, Belousov discovered the BZ reaction, and it has been the most frequently evaluated active chemical medium for prototyping chemical computers. The following will discuss some of the primary characteristics of this reaction. BZ reaction was found to be the first non-linear oscillator reaction. In this reaction, Ferroin(Fe)(or ruthenium) is selected as the catalyst as this provides simple oscillations, and the color alters between the reduced form (red) and the oxidized form (blue) that can be readily tracked optically. Other chemical components include sulfuric acid, potassium bromate (or sodium bromate), and malonic acid. As discussed, the change in the catalyst’s behavior is typically associated with the color change [4,22-27].

Chemical Computing Applications: Language Recognition

Basic concepts of computer science

The grammar produces languages. In Chomsky’s hierarchy which was introduced in 1956, grammar is categorized into four types; as illustrated in Figure 1, type0 is unrestricted or enumerable grammar. Type1 is known as context-sensitive grammar. Type2 is context-free grammar, and type3 is a regular grammar that is the most restricted one [27, 28]. The concept of language recognition is a process by information consisting of a sequence of ‘‘symbols’’ that belongs to an alphabet in a language and are fed to a computing device (automata) in sequences. Automata recognize the symbols and checks with some rules, finally delivering an output, such as

Figure 1. The Chomsky hierarchy

 

Alan Turing invented Turing Machine in 1936. Turing Machine accepts enumerable languages generated by Type-0 Grammar [29]. A Turing Machine is a powerful theoretical model for computation. Despite its simplicity, it can solve any problem with a probable solution, no matter how complicated it is. It was found to be a direct relationship between the language complexity and the capacities of the automata that recognize the language. Turing machine is the most potent automata.

The automata that compute comprises no less than one ‘‘Finite Automata’’ (FA), one or more ‘‘tapes’’ and potentially have one or more ‘‘stacks.’’ The FA is a machine answering to symbols, presumes a finite number of predetermined states, producing some precise response that depends on the input. The tape is a construct within which a problem sequence of symbols is consecutively supplied to the FA. The tape can have particular symbols, including ‘‘#’’, to reveal the sequence’s beginning and end. When necessitated by the language type, an FA can be supplemented with a ‘‘stack’’: another construct endowed with surplus rules allowing temporary storage (memory), retrieving the information during the process. Regarding the languages they acknowledge and their place in the Chomsky hierarchy, automata can be categorized into a hierarchy, as revealed in Table 1. The easiest, finite automata (FA), can detect regular languages. One-stack push-down automata (1-PDA) detecting context-free languages are the next in the hierarchy. Turing Machines (equivalent to a PDA with two or more stacks) which recognize context-sensitive and enumerable language are at the top of this hierarchy [30-36].

Chemical Implementation of Language Recognition

One of the essential applications of chemical computing is language recognition which some researchers have worked on. The first chemical Turing machine was patented and operated using the BZ reaction’s non-linear dynamics in 2017 [37]. This Turing Machine is capable of recognizing Type 1 Chomsky hierarchy. After that, a Turing Machine for Type 1, Type 2, and Type 3 was implemented in 2019 [38]. In the following, we will discuss how to implement the chemical turing machine.

Table 1. Grammars, language, and accepting automata

A primary factor in implementing chemical automata is how to select and assign the chemicals that represent the machine symbols and the input alphabete. A series of symbols from a chemical alphabet serve as the representation of the input to be computed. In this sequence, each letter demonstrates (is translated) a certain constant amount, or aliquot, of a carefully selected reacting chemical species. A one-pot reactor receives the input aliquot by aliquot at regular intervals. [37,38]. Each letter’s process (that is completely performed by chemistry) comprises its chemical species that can selectively activate particular pathways in a chemical reaction mechanism and change the extent of the reaction systematically. Every symbol is provided a specified amount of time to process it before the next symbol is added. This interval was selected through an experiment based on quick dissipation. After all, the computation's output is in the form of a specific chemical reaction. And for a given automata/language combination, the chemical behavior correlated with rejected sequences is dissimilar from the chemical behavior correlated with the accepted sequences or ‘‘words in the language of the automaton’’. The computation’s result is reaction-generated signatures that do (Accept) or do not (Reject) match a predetermined language and automaton-dependent pattern, as seen in Figure 2.

The following describes the method. First, a particular and well-recognized language from a level in the Chomsky hierarchy will be chosen to be identified by the chemical automata. Then, the class of automata needed to recognize the language (as depicted in Table 1). This is translated into distinct criteria for the chemical automata reaction and the makeup of the chemical species involved (whether they are reactants, products, or intermediates). The chemical requirements lead us to a proper chemical selection to alphabetically present the symbols. After that, the particular quantitative recipes for the preliminary circumstances and alphabet aliquots are chosen by considering practical experimental realization considerations (so that the chemical reaction monitoring system can detect automaton responses). Finally, a comprehensive set of sequences are tested experimentally, some belonging to the language accepted by the automata and others not belonging to the language [36-40].

Table 2 summerizes the reactions and details related to the implementation of each type of automata in the Chomsky hierarchy.

Figure 2. Implementation of language recognition by chemical automata [37]

 

Chemical Computing Applications: Image Processing

Basic concepts of computer science

Image processing is converting a picture from its original form into a digital form and applying certain operations to gain some useful information. A computer does this, and the pictures are analyzed. Restoration and reconstruction, improvement of low-contrast or noisy pictures, segmentation of pictures to some parts, and pattern recognition are some operations done by image processing [41-43]. Pattern recognition is classifying input data into objects, classes, or categories using computer algorithms based on critical features or regularities [45, 46]. In conventional computers, all operations are done sequentially, while chemical processors can be done in parallel [47].

Chemical Implementation of Image Processing

Experiments in [48-52] demonstrated that using the oscillating BZ reactions for basic image-processing operations was possible. This is done by a thin layer including the BZ catalyst (Ru) and a BZ reaction. As mentioned, we can have a parallel image processor by utilizing the light-sensitive chemical reaction, unlike conventional sequential computers. If the reaction proceeds in a thin layer of catalyst, spontaneous breaking of spatial symmetry occurs, and the propagation of chemical waves is noticed. We have two kinds of waves; if the catalyst is in an oscillatory regime and the period of oscillations depends on the spatial coordinate, then “phase wave” spreads over the layer. “trigger wave” is the other type of wave that is generated autocatalytic.

Table 2. Implementation details of each type of language and Automata in Chomsky hierarchy

Feedback is related to diffusion in the excitable regime. These waves propagate with steady velocity following a reaction-diffusion mechanism. By projecting a half-tone image to a skinny layer of catalyst, mild depth is varied as a characteristic of optical density and spatial coordinate. Finally, the chemical wave phenomena are influenced accordingly, and several reaction regimes may be observed in the same layer. We are capable of demonstrating contrast modification in the picture, distinguishing contours, and clearing of destroyed pictures (Figure 3) [48]. Table 3 depicts the composition of the BZ reaction for image processing. For contrast modifications used composition 1 and for distinguishing contours and clearing destroyed pictures used composition 2.

In [53] is presented a programmable chemical processor which works based on BZ reaction and consists of a reaction array of 25 switchable cells. This processor can perform pattern recognition.

Table 3. Composition of the BZ reaction


Figure 3. Image processing by chemical reaction[48]. (1) controlling the contrast in the image. (2) distinguishing contours in the image. (3) clearing of destroyed pictures

 

Conclusion

Chemical computing is a powerful emerging technology for designing unconventional computing. In this research study, first, we focused on basic concepts of chemical computing. Then we highlighted its applications and discussed its critical applications, including language recognition, image processing, and pattern recognition, and recently published studies in this field,which are evaluated and discussed. Research on this emerging technology continues.

Acknowledgment

The authors would like to appreciate the support received from the Engineering Department of the Lorestan University, Iran.

Disclosure statement

The authors reported no potential conflict of interest.

ORCID

Maryam Isvandi : 0000-0002-6150-8436

Bahman Ravaei : 0000-0003-3468-3201

Rahman Alizadeh : 0000-0002-2426-9931

[1] G.E. Moore, Electronics, 1965, 38, 114-118. [Google Scholar]  
[2] T. Gramss, S. Bornholdt, M. Gross, M. Mitchell, T. Pellizzari, Non-standard computation: molecular computation, cellular automata, evolutionary algorithms, quantum computers, Wiley-VCH: Germany, 1998, p 235. [Google Scholar], [Publisher]
[3] C. Calude, G. Paun, Computing with cells and atoms: an introduction to quantum, DNA and membrane computing, Taylor and Francis: London, 2000, p 319. [Google Scholar]
[4] A. Adamatzky, B.D.L. Costello, T. Asai, Reaction–diffusion computers, Elsevier: New York, 2005,p 334. [Google Scholar]
[5] A. Adamatzky, B.D.L. Costello, L. Bull, S. Stepney, C. Teuscher, Unconventional computing, Luniver: UK,  2007, p 332. [Google Scholar]
[6] Y. Suzuki, M. Hagiya, H. Umeo, A. Adamatzky, Natural computing, Springer: Tokyo, 2009, p 259. [Google Scholar]
[7] R.R. Feynman, The Feynman lectures on computation, Addison-Wesley: US, 1996, p 319. [Google Scholar]
[8] J. Von Neumann, The Computer and the Brain, Yale University Press: US, 1958, p 99. [Google Scholar]
[9] S. Sharifi, J. Chem. Rev., 2021, 3, 273-289. [CrossRef], [Google Scholar], [Publisher]
[10] M. Isvandi, Int. Jour. Nansci. Nanotech., 2020, 16, 167-179. [Google Scholar], [Publisher]
[11] Y. Gao, A.R. Cross, R.L. Armstrong, J. Phys. Chem., 1996, 100, 10159–10164. [CrossRef], [Google Scholar], [Publisher]
[12] A. Tóth, K. Showalter, J. Chem. Phys., 1995, 103, 2058–2066. [CrossRef], [Google Scholar], [Publisher]
[13] I.N. Motoike, A. Adamatzky, Cha. Sol. Frac., 2005, 24, 107-114. [CrossRef], [Google Scholar], [Publisher]
[14] J. Gorecki, K. Gizynski, J. Guzowski, J.N. Gorecka, P. Garstecki, G. Gruenert, P. Dittrich, Phil. Trans. R. Soc. A., 2015, 373, 20140219. [CrossRef], [Google Scholar], [Publisher]
[15] W.M. Stevens, A. Adamatzky, I. Jahan, B. de Lacy Costello, Phys. Rev. E., 2002, 66, 046112. [CrossRef], [Google Scholar], [Publisher]
[16] M.Z. Sun, X. Zhao, Chem. Phys., 2013, 138, 114106. [CrossRef], [Google Scholar], [Publisher]
[17] N.G. Rambidi, T.O.O. Kuular, E.E. Makhaeva, Adv. Mater. Opt. Electr., 1998, 8, 163–171. [CrossRef], [Google Scholar], [Publisher]
[18] A.L. Wang, J.M. Gold, N. Tompkins, M. Heymann, K.I. Harrington, S. Fraden, Eur. Phys. J. Spec. Top., 2016, 225, 211-227. [CrossRef], [Google Scholar], [Publisher]
[19] K. Gizynski, J. Gorecki, Phys. Chem. Chem. Phys, 2017, 19, 28808–28819. [CrossRef], [Google Scholar], [Publisher]
[20] K. Agladze, N. Magome, R. Aliev, T. Yamaguchi, K. Yoshikawa, Phys. D Nonlinear Phenom., 1997, 106, 247–254. [CrossRef], [Google Scholar], [Publisher]
[21] A. Adamatzky, B.D.L. Costello, C. Melhuish, N. Ratcliffe, Mater. Sci. Eng. C, 2004, 24, 541–548. [CrossRef], [Google Scholar], [Publisher]
[22] A. Adamatzky, J. Holley, P. Dittrich, J. Gorecki, B.D.L. Costello, K.P. Zauner, L. Bull, Biosystems, 2012, 109, 72-77. [CrossRef], [Google Scholar], [Publisher]
[23] A. Pechenkin, Biol. Theory, 2009, 4, 196–206. [CrossRef], [Google Scholar], [Publisher]
[24] A. Pechenkin, P Belousov and his reaction. J. Biosci., 2009, 34, 365–371. [CrossRef], [Google Scholar], [Publisher]
[25] A.T. Winfree, J. Chem. Educ., 1984, 61, 661–663. [CrossRef], [Google Scholar], [Publisher]
[26] A.K. Dutt, S.C. Müller, J. Phys. Chem., 1993, 97, 10059–10063. [CrossRef], [Google Scholar], [Publisher]
[27] F. Hoppensteadt, E. Izhikevich, Phys. Rev. Lett., 1999, 82, 2983–2986. [CrossRef], [Google Scholar], [Publisher]
[28] N. Chomsky, IRE Trans. Inform. Theory, 1956, 2, 113–124. [CrossRef], [Google Scholar], [Publisher]
[29] A.M. Turing, Proc. Lond. Math. Soc., 1937, 42, 230–265. [CrossRef], [Publisher]
[30] J.E. Hopcroft, R. Motwani, J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Longman Publishing Co, 2006. [Google Scholar]
[31] T.A. Sudkamp, Languages and Machines: An Introduction to the Theory of Computer Science, Pearson Education, 2006. [Google Scholar]
[32] E. Rich, Automata, Computability, and Complexity. Theory and Applications, Pearson/Prentice-Hall, 2008. [Google Scholar]
[33] J.G. Brookshear, Theory of Computation: Formal Languages, Automata and Complexity, Addison Wesley, 1989. [Google Scholar]
[34] D. Cohen, John Wiley & Sons, 1991. [Google Scholar]
[35]M.A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, Longman Publishing Co. 1978. [Google Scholar], [Publisher]
[36]A.G. Oettinger, Proc. Sympos. Appl. Math., 1961, 12, 104–129. [Google Scholar], [Publisher]
[37] J. Pe´rez-Mercader, M. Dueñas-Díez, D. Case, Chemically-Operated Turing Machine, US Patent, 2017, 9, 582,771 B2. [Google Scholar], [Publisher]
[38] M. Dueñas-Díez, J. Pérez-Mercader,  iScience. 2019, 19, 514–526. [CrossRef], [Google Scholar], [Publisher]
[39] D.B. Searls, Biopolymers, 2013, 99, 203–217. [CrossRef], [Google Scholar], [Publisher]
[40] M. Dueñas-Díez, J. Pe´rez-Mercader, The Energetics of Computing in Life and Machines, 2019, 119–139. [Google Scholar], [Publisher]
[41] W. Burger, M.J. Burge, Principles of Digital Image Processing: Fundamental Techniques, Springer Science & Business Media: London, 2009, 261. [Google Scholar]
[42] W. Burger, M. J. Burge, Principles of Digital Image Processing: Core Algorithms, Springer Science & Business Media, London, 2009, 332. [Google Scholar]
[43] A. Rosenfeld, Digital Picture processing: Elsevier, New York, 1982. [Publisher]
[44] R.C. Gonzalez, R.E. Woods, Digital Image Processing 4th edition: pearson, New York, 2018. [Google Scholar]
[45] C.M. Bishop, Pattern Recognition and Machine Learning, Springer, New York, 2006, 738. [Google Scholar], [Publisher]
[46] P. Foggia, G. Percannella, M. Vento, Int. Jour. Pat. Recog. Art. Intel., 2014, 28. [CrossRef], [Google Scholar], [Publisher]  
[47] S.M. Sze, Physics of Semiconductor Devices: John Wiley, New York, 1981. [Google Scholar]
[48] L. Kuhnert, K.L. Agladze, V.I. Krinsky, Nature, 1989, 337, 244-247. [CrossRef], [Google Scholar], [Publisher]
[49] K. Agladze, S. Obata, K.Yoshikawa, Physica D., 1995, 84, 238-245. [CrossRef], [Google Scholar], [Publisher]
[50] K. Bar-Eli, S. Reuveni, J. Phys. Chem., 1985, 89, 1329-1330. [CrossRef], [Google Scholar], [Publisher]
[51] R.J. Field, M. Burger, Oscillation and Travelling, Oscillation and Travelling Waves in Chemical Systems, Wiley Interscience: New York, 1985. [Google Scholar],
[52] A. Adamatzky, IEICE Trans. Electron., 2004, 11, 1748-1756. [Google Scholar], [Publisher]
[53] J.M. Parrilla-Gutierrez, A. Sharma, S. Tsuda, G.J. Cooper, G. Aragon-Camarasa, K.  Donkers, L. Cronin, Nat Commun, 2020, 11, 1-8. [CrossRef], [Google Scholar], [Publisher]