Journal of Robotics, Networking and Artificial Life, Vol. 5, No. 1 (June 2018) 6–9___________________________________________________________________________________________________________Natural Computing Paradigm ─ A Concise Introduction
Takashi Yokomori
Department of Mathematics, Faculty of Education and Integrated Arts and Sciences,
Waseda University, Tokyo 169-8050, Japan
E-mail: yokomori@waseda.jp

Abstract
Natural computing (NC) is an emerging area of research that investigates computing techniques and models inspiredby nature on one hand, and it also investigates phenomena taking place in nature in terms of computational
methodologies on the other hand. Thus, research in NC congenitally has interdisciplinary flavor, which bridges
between computer science and various disciplines of natural science. Because of its interdisciplinary nature, NC
connects and covers a broad spectrum of fundamental research fields including biology, chemistry, physics, medicalscience, and so forth. In this article, we give a concise introduction to the new computing paradigm of NC.
Specifically, we give an overview of selected topics of the fields from theory to experiments, where the stress is
primarily put on theoretical achievements in computing paradigms called molecular computing and chemical reaction
computing.

Keywords: Natural computing, molecular computing, self-assembly, chemical reaction computing.

has edited a special issue in a journal entitled MolecularComputing Paradigms. His initial efforts in the early daysof molecular computing have been succeeded by Head's

1. Introduction
Natural computing (NC) is a novel computing paradigm
inspired by nature in which NC concerns a variety ofcomputational aspects and potential features found innatural phenomena. Also, NC has close relations tocomputational process inspired by those phenomena.
The goal of NC includes the following research themes.
(i) From nature to information processing which means
investigating computational mechanism and its
implementation based on lessons from nature, and(ii) From information processing to nature which meanscomputational analysis of nature in terms of designing
new computing models and computer experiments(simulations). Further, NC also intends to exploit new
applications in the fields of various disciplines involved.
It is rather surprising that the conceptual source of theidea of NC has already appeared in an article of Biofizika
in 1973 where an idea of cell molecular computers wasdiscussed. Since 1974 Conrad has been conducting
consistent research on the information processing
capability using macro-molecules (such as proteins), andCopyright © 2018, the Authors. Published by Atlantis Press.
This is an open access article under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
6

Journal of Robotics, Networking and Artificial Life, Vol. 5, No. 1 (June 2018) 6–9___________________________________________________________________________________________________________

original work on Splicing Systems and Languages
whose theoretical results on splicing phenomena should
be highly appreciated, in that it was the first achievement
by means of mathematical analysis on bio-chemicaloperations of DNA recombination. It is possible todiscuss about new computing paradigms inspired bynature with a general schema of “Computing with X”,
where X ranges from various sorts of materials to thoseof principles. Figure 1 illustrates a part of natural
computing paradigms proposed so far within the“Computing with X” schema.
In this short article, among various computing
paradigms we take up two computing paradigms“Molecular computing” (from materials), and “Chemicalreaction computing” (from principles), and give anoutline of fundamental results on computing capability ofthese new challenging ingenuity.

Figure 2 illustrates the overview of computation schema
based on self-assembly.
In this section, we will briefly review one of the typicalmodels based on self-assembly computation, called YAC
model. Based on a unique normal form grammar G(proposed by Geffert) that can generate any recursively
enumerable language, a computing model YAC has been
proposed, in which an input string and every rule in G
are translated(encoded) into specific forms of twodimensional structural molecules. These basic blocks(units) of structural molecules with sticky ends aredesigned so that they may form a DNA complex linearlygrowing by self-assembly property. This means that YAC
performs a simulation of computation (generation) by G,
where the input string is accepted by YAC if and only if
the final DNA complex forms a completely hybridized
double-stranded (that is a desired constraint to be checkedby screening mechanism).
It is shown that any recursively enumerable language canbe recognized by YAC model. Thus, the following holds.

2. Molecular Computing Paradigm
In the early days, the goal of molecular computing
seemed to replace silicon-based hardware with biomolecular one. Unlike this intention of the early schema,
however, by now it is commonly recognized thatmolecular computers should explore challenging
applications unsuitable for existing computers.
In the theory of molecular computing, a variety ofcomputation models have been proposed and investigated.
Among others the models of computation based on selfassembly are well recognized to be of great importance inthat they can provide one of the most basic
frameworks for molecular computing paradigms. In fact,
Adleman's groundbreaking wet lab experiment [1](solving a small instance of the Hamiltonian PathProblem) is a typical example of molecular computation
based on the self-assembly principle.
When we make a brief revisit to the Adleman's original
work in 1994, it turns out that his algorithm may beformulated into the schema where component structuresare sophisticatedly encoded into linear molecules. Fromthese observations, a general schema of “one pot” selfassembly computation model is outlined as follows:
1. design a finite set of basic units for assemblycomputation (one may take this finite set as amolecular program),
2. put all those basic units with sufficiently highconcentration into one pot, to create a random poolof a single pot (that is, leave the pot for a certain
time period, resulting in producing all possible
assembly of basic units),
3. (if necessary) perform screening operations toextract only necessary (or unnecessary) assemblyof basic units,
4. detect whether or not there is an assembly withdesired constraints, then answer yes if there is, andno otherwise.

Proposition 1. ([2]) There effectively exists a computing
model based on self-assembly principle whose
computational power is Turing universal.
Other molecular computing models using highdimensional structures have been proposed to solve NPcomplete problems such as the satisfiability (SAT)
problem by Jonoska et al., where 3-dimensional graphstructures are used and the algorithm for SAT runs in time
proportional to the number variables involved in a given
formula. On the other hand, Yokomori investigated aself-assembly computing model in an abstract level,
called Computing by Conformational Change (CCC),
and proposes the following general schema that(Computation)=(Self-Assembly)+(Screening Mechanism),

where “self-assembly” is due to hybridization of either
uncorded or coded molecular components, while“screening mechanism” is regulated by either natural or
artificial constraint ([2]).

7

Journal of Robotics, Networking and Artificial Life, Vol. 5, No. 1 (June 2018) 6–9___________________________________________________________________________________________________________

3. Chemical Reaction Paradigm
Inspired by the work of reaction systems (initiated by [3]),the notion of reaction automata has been introduced in [4]by extending sets in each reaction (of a reaction system)to multisets. We start this section by reviewing basic
notions concerning reaction automata.
For a finite set S, a reaction in S is a 3-tuple a = (Ra,Ia, Pa) of finite multisets, such that Ra, Pa ∈ S#, Ia ⊆ Sand Ra ∩ Ia =, where S# denotes the set of all finite
multisets over S. The multisets Ra and Pa are called thereactant of a and the product of a, respectively, while theset Ia is called the inhibitor of a. These notations areextended to a multiset of reactions. A reaction a = (Ra, Ia,Pa) is applicable to a multiset D if Ra⊆D and Ia∩ D=.
As a result, D' (=(D-Ra)∪Pa) is derived.
With a simple example, we introduce the notion ofreaction automata. Let us consider a reaction automaton(RA) ࣛ= (S, , A, D0, f) defined as follows:
S = { p0, p1,a, b, a', f } (symbols of objects),
={a, b} (input symbols),
A = {a0, a1, a2, a3, a4 } (reactions)}, wherea0 = ( p0, aba', f ), a1 = ( p0a, b, p0a' ), a2 = ( p0 a'b, , p1 ),a3 = ( p1, a'b, a, p1 ), a4 = ( p1, aba', f),
D0 = p0 (an initial multiset), and f is the final symbol.

Figure 3. A graphic illustration of interactive
processes for accepting strings in L={anbn | n ≧ 0}.
Proposition 2. ([4,5]) The computing power of reaction
automata in maximally parallel manner coincides withthat of reaction automata in sequential manner with input mode. Further, both of those computing powers are
Turing universal.
On the other hand, the equivalence may not hold forreaction automata in sequential manner with ordinary
input mode (i.e., without the use of -input mode).
Proposition 3. ([5]) There exists a recursively enumerable language which cannot be accepted by any reaction
automaton in sequential manner.

Let w=aabb be a given input string. Since ࣛ has the initial
multiset D0 (=p0), there is no reaction in A applicable to D0.
When receiving the 1st a of w, the multiset D0 of ࣛ becomes
p0a to which only a1 is applicable and, as a result, D1 (=p0a') isderived. On receiving the 2nd a, the multiset of ࣛ becomes
p0a'a from which D2 (=p0a'a') is derived by applying a1. Then,receiving b and applying a2 lead D2 to D3 (=p1a'), and onreceiving the final b, ࣛ makes D3 into D4 (=p1) by a3. After
applying a4, D4 eventually leads to the final multiset f. Thus, an
input string aabb is accepted by ࣛ . This example shows asuccessful reaction process of ࣛ performed in sequential
manner and the set of strings thus accepted by ࣛ is denoted byLsq(ࣛ).

In order to study the role of inhibitors of reactions in thecomputing power of RAs, we introduced and studied arestricted RA called Chemical Reaction Automaton(CRA) in which no inhibitor is allowed ([6]).
Further, the space complexity issues of reaction
automata (RAs) have been considered. By restricting thevolume (i.e., the state of an RA) used in reaction process
for a successful computation, some subclasses of RAs
were introduced and investigated on relations between
classes of languages accepted by those subclasses of RAs
and language classes in the Chomsky hierarchy.
Let f(x) be a function defined on the set of natural
numbers and X in {sq, mp}. The workspace of ࣛ for w
is intuitively defined as the mini-max size of multisets(appearing in all reaction sequences) necessary for
accepting w. Then, an RA ࣛ is said to be f(n)-bounded
if for any w in LX(ࣛ) with n=|w|, the workspace of ࣛ for
w is bounded by f(n). Then, four classes of RA languages
have been investigated.
Suppose that an RA ࣛ is f(n)-bounded. If a function
f(n) is a constant k (linear, exponential), then ࣛ is termed
constant-(resp. linear-, exponential-) bounded. The classof languages accepted by constant-bounded RAs (linearbounded RAs, exponential-bounded RAs, RAs, CRAs) inX manner is denoted by(resp.,,). The class of languages accepted byconstant-boundedRAs(linear-boundedRAs,exponential-bounded RAs, RAs, CRAs) in X mannerwith -input mode is denoted by(resp.,,Figure 3 illustrates an overall view of possible reaction
processes in ࣛ with inputs anbn for n ≧ 0, and we seethat Lsq(ࣛ) = { anbn | n ≧ 0 } which is a context-freelanguage. We remark that this interactive process can bealso performed by ࣛ in maximally parallel manner, i.e.
in the manner that every applicable reactions areperformed exhaustively. That is, it holds thatLmp(ࣛ)=Lsq(ࣛ).
Besides both manners of applications in RAs, we often
consider an extension of the sequential manner where RA
allows a reaction without receiving any input symbol ateach step, which is called sequential manner with-inputmode.
We investigated the accepting powers of reaction
automata with these manners of applying reactions, andobtained the following.

8Journal of Robotics, Networking and Artificial Life, Vol. 5, No. 1 (June 2018) 6–9___________________________________________________________________________________________________________,).
The results on whole view of language class relations
are summarized in Figure 4, wheredenotes the class of regular (resp. context-free, contextsensitive, recursively enumerable) languages in Chomsky
hierarchy. Further,denotes the class of languages
generated by Petri net systems. Thus, except for theclass, each class in Chomsky hierarchy is exactly
characterized by a subclass of RA languages. Further, thefollowing result has been obtained.
Proposition 4. ([6,7]) A language L is in
if and only if L is a homomorphic
image of some language in.

Figure 4. The diagram of the relations among RA
language classes and Chomsky hierarchy. (A solidarrow denotes a proper inclusion.)

4. Broader Perspective
Natural computing, (NC) comprises a very broad rangeof computational principles that varies from wellestablished classical research areas to newly emerging
dynamical research areas with great potentiality of many
promising applications to interdisciplinary fields.
The former family may include Cellular computation,
one of the oldest computing models studied since late1940s. In Neural computation, artificial neural networks
are proposed as computing systems inspired by the
biological neural networks mimicking brain functions.
Evolutionary computation provides a bunch ofalgorithms for global optimization strategy inspired bybiological evolution. Further, Artificial life is a longlasting research theme from which artificial immune
algorithms have been lately developed. As for the latterfamily of research areas in NC, there are quite a few
topics to be mentioned, while due to the space limit wecan regretfully name only a part of those emergence offascinating thoughts here: Membrane computation,Reaction-diffusion computation, Optical computation,
Quantum computation, Swarm intelligence, etc.
Further, their applications to practical problems in thereal world such as drug discovery in “nano-levelengineering” and “medical/life science” are highly
recommended to be tackled. For one example, one may
refer to a medical application, lately reported, of the useof C.elegans for detecting cancer patients.
Finally, the reader interested in more details about
topics discussed here and other many subjects in NC iscordially advised to consult reference papers orappropriate bibliographic sources (such as [8,9,10]).

References
1.

L. Adleman, Molecular Computation of Solutions toCombinatorial Problems, Science, vol.266, pp.1021-1024,
1994.
2. T. Yokomori, Computation = Self-assembly + Conformational Change: Toward New Computing Paradigms,
Proc. of 4th International Conference on Developments inLanguage Theory DLT'99, Aachen, July, pp.21-30, 1999.
3. A. Ehrenfeucht and G. Rozenberg, Reaction systems,
Fundamenta Informaticae vol.75, pp.263-280, 2007.
4. F. Okubo, S. Kobayashi and T. Yokomori, Reaction
Automata, Theore. Comput. Sci., 429, pp.247-257, 2012.
5. F. Okubo, On the Computational Power of Reaction
Automata Working in Sequential Manner, 4th Workshop
on Non-Classical Models for Automata and Applications,
book@ocg.at series 290, pp.149-164, Osterreichische
Computer Gesellschaft, 2012.
6. F. Okubo and T. Yokomori, The Computational
Capability of Chemical Reaction Automata, NaturalComputing, 15, pp.215-224, 2016.
7. F. Okubo, S. Kobayashi and T. Yokomori, On theProperties of Language Classes Defined by Bounded
Reaction Automata, Theore. Comput. Sci., 454, pp.206221, 2012.
8. Gh. Pӑun, G. Rozenberg, A. Salomaa (Eds.), Handbook ofMembrane Computing, Oxford Univ. Press, 2010.
9. G. Rozenberg, T. Bäck and J.N. Kok (eds.), Handbook of
Natural Computing, 4 Volumes, Springer, 2012.
10. M.Hagiya and T.Yokomori (eds), Natural Computing
Series: Vol.0-Vol.7, Kindai Kagaku-sha ， 2011 (inJapanese)．

Acknowledgements
The work partly supported by Partly supported by JSPS
KAKENHI, Grant-in-Aid for Scientific Research (C)17K00021 of The Ministry of Education, Culture, Sports,
Science, and Technology, Japan, and by Waseda University
grant for Special Research Project: 2017K-121.

9