Next Article in Journal
Towards Better Performance for Protected Iris Biometric System with Confidence Matrix
Previous Article in Journal
Lateralized Declarative-Like Memory for Conditional Spatial Information in Domestic Chicks (Gallus gallus)
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Logic Gates Formed by Perturbations in an Asynchronous Game of Life

Department of Intermedia, Art and Science, School of Fundamental Science and Engineering, Waseda University, 3-4-1, Ohkubo, Shinjuku, Tokyo 169-8555, Japan
*
Author to whom correspondence should be addressed.
Submission received: 31 March 2021 / Revised: 30 April 2021 / Accepted: 11 May 2021 / Published: 20 May 2021
(This article belongs to the Section Computer)

Abstract

:
The game of life (GL), a type of two-dimensional cellular automaton, has been the subject of many studies because of its simple mechanism and complex behavior. In particular, the construction of logic circuits using the GL has helped to extend the concept of computation. Conventional logic circuits assume deterministic transitions due to the synchronicity of the classic GL. However, they are fragile to noise and cannot maintain the expected behavior in an environment with noise. In this study, a probabilistic logic gate model was constructed using perturbations in an asynchronous game of life (AGL). Since our asynchronous automaton had no heterogeneity in either the horizontal or vertical directions, it was symmetrical with respect to spatial structure. On the other hand, the construction of the logical gate was implemented to contain heterogeneity in the horizontal or vertical directions, which could allow an AND gate and an OR gate in a single system. It was based on the phase transition between connected and unconnected phases, which is newly discovered in this study. In the model, perturbations symmetrically entail operations successful and unsuccessful, and this symmetrical double action is given not to interfere with established operations but to make operations possible. Therefore, this model had a different meaning from logic gates that exclude perturbations or use them externally. The idea of this perturbation is analogous to the inherent noise that destroys and generates structures in biological swarms.

1. Introduction

To date, various logic gates have been constructed for the GL. For example, there are logic gates that use collisions of gliders [1,2,3,4] or geographical constraints with fixed objects [5]. These logic gates are based on synchronous updating. In the classic GL, the state of the cells is updated using the states of neighbors at the same time step. Information is transmitted without delay or noise in such a synchronous GL, and its transitions are deterministic. Therefore, logic gates in a synchronous GL are fragile to perturbations and cannot maintain their behavior in environments with noise.
To address this issue, probabilistic logic gates are constructed in an AGL using perturbations. Information transmission, such as the interaction of molecules in the real world, is asynchronous, containing delay and noise [6]. The AGL is the application of asynchronicity to update the states of the cells. Specifically, the AGL is the normal GL with an asynchronous rate p async , a probability that the states of the cells will not be updated. There are many studies about such asynchronous cellular automata [7,8,9].
Furthermore, in this study, perturbations were introduced into the GL system by stochastically reversing the states of cells. In cellular automaton research, perturbations are used to prove the robustness of the system, often by adding fluctuations to a steady state externally and observing their effects [10,11,12,13]. This evaluation assumes that perturbations are external to the structure of the system and that the perturbations and the structure are in opposition [14]. However, this assumption fails to capture the possibility that perturbations are intrinsic to the structure. This research aimed to perform operations with logic gates based on a structure that does not exclude perturbations but rather is formed by internal perturbations. By making perturbations intrinsic to logic gate operations, it will be possible to approach robust computations performed in the real world with noise.
To determine the conditions under which logic gates are formed, a property of phase transitions was used. Several phase transitions with respect to asynchronous rates have been found so far [15]. One of them, which is related to this study, is a phase transition between the frozen phase and unfrozen phase. The frozen phase is the phase in which the GL system remains unchanged, with no cells in state 1 or only fixed objects or oscillators. In contrast, a phase in which the system continues to change after a certain time is called an unfrozen phase. As the asynchronous rate is increased, the GL system transitions from a frozen phase to an unfrozen phase near the critical point p async = 0.1269 [16].
Based on the above, the difference between the phases shown in Figure 1 was the focus of this study. These patterns belong to the unfrozen phase and continue their transitions, showing similar patterns. The maze-like pattern (right column) is known as the labyrinth phase (LP) [13], and some phase transitions about the LP have been found so far [12,17]. However, the critical points of these phase transitions belong to the frozen phase, and the difference between the phases in the unfrozen phase has not been found. Therefore, to investigate the difference in these phases, a new definition is necessary.

2. Materials and Methods

The maze-like pattern was defined as a “connected state” in this study. A connected state is determined by the following process:
  • A cell in state 1 at edge 1 of the system is set to x;
  • If there is a cell in state 1 in the Moore neighborhood of x, then set it to x;
  • Repeat process 2;
  • If x is at edge 2 of the system, then edge 1 and edge 2 are connected, and the system is determined to be in a connected state.
Figure 2 shows an example of a system in a connected state. The red cells are cells that have ever been set to x. This “path” runs from the upper edge to the lower edge of the system. This means that these edges are connected, and this system is in a connected state.
In our experiments, perturbations were added by flipping the states of cells at the perturbation rate p noise . The AGL, perturbation, and evaluation of connectivity were performed by the following program:
For each cell at site ( i ,   j )
temporary   state i , j t + 1 = state i , j t with   probability   p async
temporary   state i , j t + 1 = f ( state i , j t , sum i , j t )   with   probability   1 p async
For each cell at site ( i ,   j )
If   temporary   state i , j t + 1 = 0   then   state i , j t + 1 = 1   with   probability   p noise state i , j t + 1 = 0   with   probability   1 p noise
If   temporary   state i , j t + 1 = 1   then   state i , j t + 1 = 0   with   probability   p noise state i , j t + 1 = 1   with   probability   1 p noise
Evaluate whether the edges are connected
Repeat until T max
where
state i , j t   is   the   current   state :   0   or   1 .
temporary   state i , j t + 1 is not the actual state of the cell. It is used to add perturbations and determine the next state.
sum i , j t = m = 1 ,   n = 1 m = + 1 ,   n = + 1 state i + m , j + n t state i , j t
f ( 0 ,   0 ) = 0 f ( 1 ,   0 ) = 0
f ( 0 ,   1 ) = 0 f ( 1 ,   1 ) = 0
f ( 0 ,   2 ) = 0 f ( 1 ,   2 ) = 1
f ( 0 ,   3 ) = 1 f ( 1 ,   3 ) = 1
f ( 0 ,   4 ) = 0 f ( 1 ,   4 ) = 0
f ( 0 ,   5 ) = 0 f ( 1 ,   5 ) = 0
f ( 0 ,   6 ) = 0 f ( 1 ,   6 ) = 0
f ( 0 ,   7 ) = 0 f ( 1 ,   7 ) = 0
f ( 0 ,   8 ) = 0 f ( 1 ,   8 ) = 0
Connectivity is evaluated by the following program:
For each cell at site ( i 0 ,     j 0 ) on edge 1,
i.e., i 0 = 1 , i 0 = N , j 0 = 1 , or j 0 = N ,
  • Initialize the path list;
  • If state i 0 , j 0 = 1 , then i order = i 0 , j order = j 0
    add tuple ( i 0 , j 0 ) to the path list;
  • If state i order + m ,   j order + n = 1 and
    ( i order + m ,     j order + n ) is not included in the path list,
    then i order = i order + m ,     j order = j order + n
    add tuple ( i order ,     j order ) to the path list
    repeat process 3 recursively;
  • If the cell at site ( i order ,     j order ) is on edge 2,
    i.e., i order = 1 , i order = N , j order = 1 , or j order = N ,
    then edge 1 and edge 2 are connected
where
N is the system size
If   i = 1 ,   then   the   edge   is   on   the   left   side
Or   if   i = N ,   then   the   edge   is   on   the   right   side
If   j = 1 ,   then   the   edge   is   on   the   lower   side
Or   if   j = N ,   then   the   edge   is   on   the   upper   side
1 m + 1 ,   1 n + 1
1 i order + m N ,     1 j order + n N

3. Results

First, the existence of the phase transition of connectivity was examined. Figure 3 shows the percentage of trials in which the top and bottom edges and the left and right edges were simultaneously connected at least once by T max = 10 , 000 . No perturbations were added. The system was 100 by 100 cells and had periodic boundaries. One hundred trials were made at each asynchronous rate. There were two phases: a connected phase in which connections were likely to occur and an unconnected phase in which connections scarcely occur. As the asynchronous rate is increased, the GL system transitions from the connected phase to the unconnected phase near the critical point p async = 0.350 .
Then, the effect of perturbations on the phase transition was examined. Figure 4 shows the connectivity at various perturbation rates. Five different perturbation rates were used. In each graph, there are phase transitions between the connected phase and unconnected phase, such as when there were no perturbations ( p noise = 0.00 % ). The critical point decreased as the perturbation rate increased. This property can also be confirmed by the parameters of the fitting function shown in Table 1. Hence, the results for p noise = 0.00 % and p noise = 0.01 % were very different from those for p noise = 2.00 % at approximately p async = 0.350 . Considering this difference in the phases, a logic gate model was designed.
A fitting function is a sigmoid represented by 1 1 + exp [ a ( x b ) ] .
In this study, the GL system was taken as an analogy with electric circuits; a connection of the edges of the system was read as an energization of the circuit. As mentioned above, simply put, if perturbations are added to the system, then connections occur, and if no perturbations are added, then no connections occur at certain values of the asynchronous rate. Then, a correspondence can be made with electric circuits that energize if there is a conductor and do not energize if there is no conductor. Since the connection is mapped to the energization, the presence/absence of perturbations can be mapped to the presence/absence of a conductor.
Figure 5 represents our probabilistic logic gate model. If the input is 1, then perturbations are added to the input area at probability p noise during a trial. If the input is 0, then no perturbations are added to the area. If connections occur during a trial, the output is 1. Otherwise, the output is 0. Note the arrangement of the input areas in the model. When they are viewed horizontally, they are in parallel. If viewed vertically, they are in series. That is, when the connection between the left edge and right edge of the system is to be output, the system is a parallel circuit, as shown in Figure 6. When the connection between the upper edge and lower edge of the system is to be output, the system is a series circuit.
In electric circuits, if the inputs are to be the presence or absence of conductors and the output is to be energized or not, the series circuit becomes an AND gate and the parallel circuit becomes an OR gate. Therefore, experiments were performed to determine whether the logic gate model could be used to implement AND and OR gates.
Figure 7 shows the output of the model. Perturbations were added at p noise = 2.00 % if the input was 1. The output was set to 1 if it was connected at least once by T max = 5000 and 0 otherwise. The system was 200 by 200 cells and had periodic boundaries. One hundred trials were made at each asynchronous rate. In both circuits, the outputs changed from 0 to 1 as the asynchronous rate increased from 0.30 to 0.40. In the middle region, the gap in the outputs between the two circuits became larger. In particular, at p async = 0.350 , fewer than 30% of the trials returned an output of 1 in the series circuit, whereas more than 70% of the trials returned an output of 1 in the parallel circuit. This is an appropriate region in which to establish both the AND gate and OR gate at the same asynchronous rate.
Figure 8 represents the outputs of two circuits for all input combinations at p async = 0.350 . The behavior of the probabilistic AND gate was obtained in a series circuit, while the behavior of the probabilistic OR gate was obtained in a parallel circuit.

4. Discussion

The aim of this study was to construct a robust logic gate using a GL. First the existence of a phase transition between connected and unconnected phases was discovered and the effect of perturbations was investigated. Then, the logic gate model was designed by using an electric circuit as an analogy. In our model, a probabilistic AND gate and probabilistic OR gate are implemented in one system around the critical point of the phase transition. The asymmetric behaviors in the vertical and horizontal directions are due to the arrangement of the input areas and the property of the phase transition. For applying this model to advanced calculations, there are two limitations. The first is the number of time steps and the computational cost required to return the output. In the model, the recursive function was called for 5000 or 10,000 time steps. Second, as the size of the system changes, the probability that the system becomes a connected state also changes; the edges are more difficult to be connected in a larger system. These constraints must be taken into account, especially when expanding the system.
In recent years, logic circuits based on two-dimensional materials have been studied in the field of nanotechnology [18]. The work of Liu et al. is similar to this work in that both AND and OR gates can be implemented with a single device, the behavior of the device can be changed depending on the parameters, and the output is stable for specific perturbations. In comparison with Liu et al.′s work, the weak point of our model is that it does not have temporal properties. In other words, the perturbation rate p noise and the rules of the GL do not change during a trial, making learning and memorization impossible. To address this issue, methods such as changing the local rule of cellular automata [19] and misrecognizing states [20] need to be considered.
On the other hand, what this research emphasizes is a method of using perturbations. In conventional logic gates in the GL, perturbations are considered to be external to the structure, and there are no perturbations in it. However, in the real world, are structure and perturbation in opposition? It is known that in groups of living creatures, even when there are no external enemies, individuals move within the group and continuously change their relative positions [21]. This perturbation is called “inherent noise”, and it has been suggested that inherent noise is an essential element for the formation of swarms [22]. The structure of the swarm does not oppose perturbations. Rather, it is destroyed and generated by perturbations and becomes dynamic. The structure of the connection in this study is also doubly affected by the perturbations of asynchronous updating and flipping states, which symmetrically entail the operation successful and unsuccessful. This symmetrical double constraint of perturbations is the reason our model works correctly. Our model is expected to be applied to explain and model the robust behavior of individuals in the swarm and fluctuating behavior when not in the swarm [23]. It can be considered a starting point for reconstructing the relationship between the two terms of structure and perturbation in the computation. The realization of inherent noise in cellular automata in a clearer form will be the subject of further study.

Author Contributions

Conceptualization, Y.O. and Y.-P.G.; Investigation, Y.O.; Software, Y.O.; Supervision, Y.-P.G.; Visualization, Y.O.; Writing—original draft, Y.O.; Writing—review & editing, Y.-P.G. All authors have read and agreed to the published version of the manuscript.

Funding

This research was funded by JPJS, grant number 00120351748.

Informed Consent Statement

Not applicable.

Data Availability Statement

The data that support the findings of this study are available from the corresponding author, Y.O., upon reasonable request.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Rennard, J.-P. Implementation of Logical Functions in the Game of Life. Collision Based Comput. 2002, 491–512. [Google Scholar] [CrossRef] [Green Version]
  2. Martínez, G.J.; Adamatzky, A.; McIntosh, H.V. Phenomenology of glider collisions in cellular automaton Rule 54 and associated logical gates. Chaos Solitons Fractals 2006, 28, 100–111. [Google Scholar] [CrossRef] [Green Version]
  3. Martínez, G.J.; Adamatzky, A.; Morita, K. Logical Gates via Gliders Collisions. In Reversibility and Universality; Adamatzky, A., Ed.; Springer: Berlin/Heidelberg, Germany, 2018; pp. 199–220. [Google Scholar]
  4. Soto, J.M.G.; Wuensche, A. Minimal glider-gun in a 2d cellular automaton. arXiv 2017, arXiv:1709.02655. [Google Scholar]
  5. Martínez, G.J.; Adamatzky, A.; Morita, K.; Margenstern, M. Computation with competing patterns in life-like automaton. Game Life Cell. Autom. 2010, 547–572. [Google Scholar] [CrossRef] [Green Version]
  6. Matsuno, K. Determinism and Freedom in Early Evolution. In Individuality and Determinism; Springer: Boston, MA, USA, 1984; pp. 203–215. [Google Scholar]
  7. Fatès, N.; Thierry, É.; Morvan, M.; Schabanel, N. Fully asynchronous behavior of double-quiescent elementary cellular automata. Theor. Comput. Sci. 2006, 362, 1–16. [Google Scholar] [CrossRef] [Green Version]
  8. Fatès, N. A guided tour of asynchronous cellular automata. J. Cell. Autom. 2014, 9, 387–416. [Google Scholar]
  9. Sethi, B.; Roy, S.; Das, S. Asynchronous cellular automata and pattern classification. Complexity 2016, 21, 370–386. [Google Scholar] [CrossRef] [Green Version]
  10. Fates, N.A.; Morvan, M. An Experimental Study of Robustness to Asynchronism for Elementary Cellular Automata. arXiv 2004. arXiv preprint nlin/0402016. [Google Scholar]
  11. Fatès, N.; Morvan, M. Perturbing the topology of the game of life increases its robustness to asynchrony. Lect. Notes Comput. Sci. 2004, 3305, 111–120. [Google Scholar] [CrossRef] [Green Version]
  12. Blok, H.J.; Bergersen, B. Synchronous versus asynchronous updating in the “game of Life”. Phys. Rev. E Stat. Phys. Plasmas Fluids Relat. Interdiscip. Top. 1999, 59, 3876–3879. [Google Scholar] [CrossRef] [Green Version]
  13. Bersini, H.; Detours, V.; Cp, I. Asynchrony Induces Stability in Cellular Automata Based models. Artif. Life IV 1994. [Google Scholar] [CrossRef]
  14. Jen, E. Stable or robust? What’s the difference? Complexity 2003, 8, 12–18. [Google Scholar] [CrossRef] [Green Version]
  15. Radicchi, F.; Vilone, D.; Meyer-ortmanns, H. Phase Transition between Synchronous and Asynchronous Updating Algorithms. J. Stat. Physics 2007, 593–603. [Google Scholar] [CrossRef] [Green Version]
  16. Gunji, Y.-P.; Ohzawa, Y.; Tanaka, T. Probabilistic Logic Gate in Asynchronous Game of Life with Critical Property. In Handbook of Unconventional Computing (in 2 Vols.); Adamatzky, A., Ed.; World Scientific Publishing Company: Singapore, 2021; pp. 375–397. [Google Scholar] [CrossRef]
  17. Fatès, N. Does Life Resist Asynchrony? In Game of Life Cellular Automata; Springer: London, UK, 2010; pp. 257–274. [Google Scholar]
  18. Liu, C.; Chen, H.; Hou, X.; Zhang, H.; Han, J.; Jiang, Y.G.; Zeng, X.; Zhang, D.W.; Zhou, P. Small footprint transistor architecture for photoswitching logic and in situ memory. Nat. Nanotechnol. 2019, 14, 662–667. [Google Scholar] [CrossRef] [PubMed]
  19. Sakiyama, T.; Gunji, Y.P. Uncertain density balance triggers scale-free evolution in game of life. Complex. Syst. 2017, 26, 31–38. [Google Scholar] [CrossRef]
  20. Nakajima, K.; Haruna, T. Self-organized perturbations enhance class IV behavior and 1/f power spectrum in elementary cellular automata. BioSystems 2011, 105, 216–224. [Google Scholar] [CrossRef] [PubMed]
  21. Murakami, H.; Niizato, T.; Tomaru, T.; Nishiyama, Y.; Gunji, Y.P. Inherent noise appears as a Lévy walk in fish schools. Sci. Rep. 2015, 5. [Google Scholar] [CrossRef] [PubMed]
  22. Murakami, H.; Tomaru, T.; Nishiyama, Y.; Moriyama, T.; Niizato, T.; Gunji, Y.P. Emergent runaway into an avoidance area in a swarm of soldier crabs. PLoS ONE 2014, 9. [Google Scholar] [CrossRef] [PubMed]
  23. Shokaku, T.; Moriyama, T.; Murakami, H.; Shinohara, S.; Manome, N.; Morioka, K. Development of an automatic turntable-type multiple T-maze device and observation of pill bug behavior. Rev. Sci. Instrum. 2020, 91. [Google Scholar] [CrossRef] [PubMed]
Figure 1. AGL systems. The systems show different patterns at p async = 0.30 (left column) and p async = 0.70 (right column). These systems continue the transition as in rows 1 to 4.
Figure 1. AGL systems. The systems show different patterns at p async = 0.30 (left column) and p async = 0.70 (right column). These systems continue the transition as in rows 1 to 4.
Symmetry 13 00907 g001
Figure 2. An example of a system in a connected state. (a) GL system. (b) This system is determined to be in a connected state because the “path” shown in red runs from one edge to another edge of the system.
Figure 2. An example of a system in a connected state. (a) GL system. (b) This system is determined to be in a connected state because the “path” shown in red runs from one edge to another edge of the system.
Symmetry 13 00907 g002
Figure 3. Phase transition between the connected phase and unconnected phase with respect to the asynchronous rate. The plots are data from experiments, and the curve is a sigmoid function fitted to the data.
Figure 3. Phase transition between the connected phase and unconnected phase with respect to the asynchronous rate. The plots are data from experiments, and the curve is a sigmoid function fitted to the data.
Symmetry 13 00907 g003
Figure 4. Phase transitions at various perturbation rates. (ae) Plots of the experimental data and curves of the fitting functions. (f) Fitting functions for all perturbation rates.
Figure 4. Phase transitions at various perturbation rates. (ae) Plots of the experimental data and curves of the fitting functions. (f) Fitting functions for all perturbation rates.
Symmetry 13 00907 g004
Figure 5. (a) Logic gate model. The arrangement of its input areas is the same as that of the conductors in (b) a series circuit when viewed vertically and that of (c) a parallel circuit when viewed horizontally.
Figure 5. (a) Logic gate model. The arrangement of its input areas is the same as that of the conductors in (b) a series circuit when viewed vertically and that of (c) a parallel circuit when viewed horizontally.
Symmetry 13 00907 g005
Figure 6. Examples of outputs in series and parallel circuits.
Figure 6. Examples of outputs in series and parallel circuits.
Symmetry 13 00907 g006
Figure 7. Outputs for the input (1, 0) in the series and parallel circuits of our model.
Figure 7. Outputs for the input (1, 0) in the series and parallel circuits of our model.
Symmetry 13 00907 g007
Figure 8. Outputs of the logic gate model at p async = 0.350 . (a) The series circuit behaved as a probabilistic AND gate, and (b) the parallel circuit behaved as a probabilistic OR gate.
Figure 8. Outputs of the logic gate model at p async = 0.350 . (a) The series circuit behaved as a probabilistic AND gate, and (b) the parallel circuit behaved as a probabilistic OR gate.
Symmetry 13 00907 g008
Table 1. Parameters of the fitting functions.
Table 1. Parameters of the fitting functions.
pnoise (%)ab
0.00118.9730.350
0.01116.7820.349
0.10113.9750.346
0.5095.4670.326
1.0095.9490.305
2.0086.3980.265
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Share and Cite

MDPI and ACS Style

Ohzawa, Y.; Gunji, Y.-P. Logic Gates Formed by Perturbations in an Asynchronous Game of Life. Symmetry 2021, 13, 907. https://0-doi-org.brum.beds.ac.uk/10.3390/sym13050907

AMA Style

Ohzawa Y, Gunji Y-P. Logic Gates Formed by Perturbations in an Asynchronous Game of Life. Symmetry. 2021; 13(5):907. https://0-doi-org.brum.beds.ac.uk/10.3390/sym13050907

Chicago/Turabian Style

Ohzawa, Yoshihiko, and Yukio-Pegio Gunji. 2021. "Logic Gates Formed by Perturbations in an Asynchronous Game of Life" Symmetry 13, no. 5: 907. https://0-doi-org.brum.beds.ac.uk/10.3390/sym13050907

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop