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
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