nach oben

2013 | Buch

Kapitel lesen Erstes Kapitel lesen

Reaction-Diffusion Automata: Phenomenology, Localisations, Computation

verfasst von: Andrew Adamatzky

Verlag: Springer Berlin Heidelberg

Buchreihe : Emergence, Complexity and Computation

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Reaction-diffusion and excitable media are amongst most intriguing substrates. Despite apparent simplicity of the physical processes involved the media exhibit a wide range of amazing patterns: from target and spiral waves to travelling localisations and stationary breathing patterns. These media are at the heart of most natural processes, including morphogenesis of living beings, geological formations, nervous and muscular activity, and socio-economic developments.

This book explores a minimalist paradigm of studying reaction-diffusion and excitable media using locally-connected networks of finite-state machines: cellular automata and automata on proximity graphs. Cellular automata are marvellous objects per se because they show us how to generate and manage complexity using very simple rules of dynamical transitions. When combined with the reaction-diffusion paradigm the cellular automata become an essential user-friendly tool for modelling natural systems and designing future and emergent computing architectures.

The book brings together hot topics of non-linear sciences, complexity, and future and emergent computing. It shows how to discover propagating localisation and perform computation with them in very simple two-dimensional automaton models. Paradigms, models and implementations presented in the book strengthen the theoretical foundations in the area for future and emergent computing and lay key stones towards physical embodied information processing systems.

Inhaltsverzeichnis

Frontmatter

Introduction

Abstract

Cellular automata are regular uniform networks of locally-connected finite-state machines, called cells. A cell takes a finite number of states. Cells are locally connected: every cell updates its state depending on states of its geographically closest neighbours. All cells update their states simultaneously in discrete time steps. All cells employe the same rule to calculate their states. Cellular automata are discrete systems with non-trivial behaviour. They are mathematical models of computation and computer models of natural systems.

Andrew Adamatzky

Phenomenology and Localisations

Frontmatter

Reaction-Diffusion Binary-State Automata

Abstract

Here we consider a simplest version of reaction-diffusion automaton: a two-dimensional cellular automaton, where a cell has eight closest neighbours and takes two states, 0 and 1. We earmark state 0 as a substrate and state 1 as a reagent. To imitate diffusion and reaction we allow state 1 to spread: a cell in state 0 takes state 1 – under certain conditions – if it has some neighbours in state 1.

Andrew Adamatzky

Retained Excitation

Abstract

In classical models of excitation an excited cells returns to refractory states either immediately or in few steps but in any case independently on a state if its neighbourhood. How space-time dynamics of excitation will change if we allow excited cells to stay excited for certain configurations of excitation in their neighbourhoods? Let us consider excitation rules which allow excitation to persist by enabling excited cells ‘support’ their already excited neighbours.

Andrew Adamatzky

Mutualistic Excitation

Abstract

In a classical Greenberg-Hasting model of excitation a resting cell excites depending on number of its excited neighbours. What if the process of being excited depends also on refractory states? Let every cell x of an automaton imitating mutualistic excitation take three states: resting ·, excited ∙, refractory ∘. and updates its state by the rule

\(x^{t+1} = \begin{cases} \bullet, \text{ if } x^t=\cdot \text{ and } \sigma_+^t(x) \in[\theta_1, \theta_2] \text{ and } \sigma_-^t(x) \in[\delta_1, \delta_2]\\ \circ, \text{ if } x^t=\bullet\\ \cdot, \text{ otherwise } \end{cases}\) (4.1)

Andrew Adamatzky

Dynamical Excitation Intervals: Diversity and Localisations

Abstract

Back in 1998 [7], we introduced an excitable cellular automaton,where a resting cell is excited if a number of its excited neighbours belong to a fixed interval [θ ₁,θ ₂]. The interval [θ ₁,θ ₂] is called an excitation interval. For two-dimensional cellular automaton with eight-cell neighbourhood 1 ≤ θ ₁ ≤ θ ₂ ≤ 8. We found that by tuning θ ₁ and θ ₂ we can persuade the automaton to imitate almost all kinds of excitation dynamics, from classical target and spiral waves observed in physical and chemical excitable media to wave-fragments inhabiting sub-excitable media [7].

Andrew Adamatzky

Excitable Delaunay Triangulations

Abstract

Given a planar finite set V the Delaunay triangulation [92] \({\mathcal D}\)(V)= 〈V, E 〉 is a graph subdividing the space onto triangles with vertices in V and edges in E where the circumcircle of any triangle contains no points of V other than its vertices. Neighbours of a node v ∈ V are nodes from V connected with v by edges from E.

The set V is constructed as follows. We take a disc-container of radius 480 and fill it with up to 15,000 disc-nodes. We assume that each disc-node has radius 2.5, thus a minimal distance between any two nodes is 5. The Voronoi diagram, and its dual triangulation, are appropriate representations of such identical sphere packing on two-dimensional surface, where planar points of V represent centres of the spheres.

Andrew Adamatzky

Excitable β-Skeletons

Abstract

Given a set \(\mathbf V\) of planar points, for any two points p and q we define β-neighbourhood U _β(p,q) as an intersection of two discs with radius β|p − q| / 2 centered at points \(((1-\frac{\beta}{2})p,\frac{\beta}{2}q)\) and \((\frac{\beta}{2}p, (1-\frac{\beta}{2})q)\), β ≥ 1 [150, 160], see examples of the lunes in Fig.7.1. Points p and q are connected by an edge in β-skeleton if the pair’s β-neighbourhood contains no other points from \(\mathbf V\).

Andrew Adamatzky

Evolving Localizations in Reaction-Diffusion Automata

Abstract

We consider a ternary-state totalistic hexagonal cellular automaton, where a cell updates its state depending on just the numbers, not positions, of different cell-states in its neighbourhoods. One cell-state, S, is a dedicated substrate state: a cell in state S, whose neighbourhood is filled only with states S, does not change its state (S is a an analogue of quiescent state in cellular automaton models). Two other states, A and B, are assigned to be reactants.

Andrew Adamatzky

Population Dynamics

Frontmatter

Population Dynamics in Automata

Abstract

Let us consider a two-dimensional hexagonal cellular automaton, every cell of which takes two states: species a and species b, and updates its state in discrete time indexautomaton!population depending on its own state and just the numbers of cell-states of its six neighbours. Let \(\sigma_a^t(x)\) and \(\sigma_b^t(x)\) be sums of cell x’s neighbours in state a and b, respectively, at time step t.

Andrew Adamatzky

Automaton Mechanics of Mutualism

Abstract

We simulate mutualistic relationships in a two-dimensional hexagonal cellular automaton. Every cell takes three states: 0, 1 and 2. States 1 and 2 represent species species ‘1’ and species ‘2’. State 0 represents an ‘empty space’, or a substrate. Two processes must be simulated: propagation of species and survival of species. A cell of the hexagonal cellular automaton can be occupied exclusively by ‘empty space’, state 0, or by one of the species, states 1 or 2.

Andrew Adamatzky

Computation with Excitation

Frontmatter

Voronoi Automata

Abstract

Let P be a nonempty finite set of planar points. A planar Voronoi diagram [253] of the set P is a partition of the plane into such regions, that for any element of P, a region corresponding to a unique point p contains all those points of the plane which are closer to p than to any other node of P. A unique region vor(p) = {z ∈ R ²: d(p,z) < d(p,m) ∀ m ∈ R ², m ≠ z } assigned to point p is called a Voronoi cell of the point p [211]. The boundary ∂ vor(p) of the Voronoi cell of a point p is built of segments of bisectors separating pairs of geographically closest points of the given planar set P. A union of VD(P) = ∪ _p ∈ P ∂ vor(p) all boundaries of the Voronoi cells determines the planar Voronoi diagram [211]. A variety of Voronoi diagrams and algorithms of their construction can be found in [162, 206].

Andrew Adamatzky

Adders and Multipliers in Sub-excitable Automata

Abstract

To implement binary arithmetics we employ a cellular-automaton model of an excitable medium — the 2⁺-medium, [2, 3, 8]. The 2⁺-medium is a two-dimensional three-state — resting (·), excited (+) and refractory (–) — cellular automaton where a resting cell becomes excited only exactly two neighbours are excited. The transitions from excited state to refractory state, and from refractory state to resting state are unconditional.

Andrew Adamatzky

Computing in Hexagonal Reaction-Diffusion Automaton

Abstract

We design a totalistic cellular automaton, where a cell updates its state depending on just the numbers of different cell-states in its neighbourhoods.Consider a ternary state automaton, where every cell takes one of the following cell-states: substrate S, activator A and inhibitor I.

Andrew Adamatzky

Semi-memristive Automata: Retained Refractoriness

Abstract

A cellular automaton \(\mathcal{A}\) is an orthogonal array of uniform finite-state machines, or cells. Each cell takes the finite number of states and updates its states in discrete time depending on states of its closest neighbours. All cells update their states simultaneously by the same rule. We consider eight-cell neighbourhood and three cell-states: resting ∘, excited +, and refractory –. Let u(x) = { y: |x − y|_L ∞ = 1} be a neighbourhood of cell x. Let \(\sigma^t_x = \sum_{y \in u(x)} \chi(y^t, +)\) be the sum of excited neighbours of cell x at time step t, where χ(y ^t, + ) = 1 if y ^t = + and χ(y ^t, + ) = 0 otherwise. Let Θ = [θ ₁, θ ₂], 1 ≤ θ ₁ ≤ θ ₂ ≤ 8, be an excitation interval, and Φ = [φ ₁, φ ₂], 1 ≤ φ ₁ ≤ φ ₂ ≤ 8, be a recovery interval.

Andrew Adamatzky

Structural Dynamics: Memristive Excitable Automata

Abstract

A memristive automaton is a structurally-dynamic excitable cellular automaton where a link connecting two cells is removed or added if one of the cells is in excited state and another cell is in refractory state.

A cellular automaton \(\mathcal{A}\) is an orthogonal array of uniform finite-state machines, or cells. Each cell takes finite number of states and updates its states in discrete time depending on states of its closest neighbours. All cells update their states simultaneously by the same rule. We consider eight-cell neighbourhood and three cell-states: resting ∘, excited +, and refractory −. Let u(x) = { y: |x − y|_L ∞ = 1} be a neighbourhood of cell x. A cell x has a set of incoming links { l _xy: y ∈ u(x)} which take states 0 and 1. A link l _xy is a link of excitation transfer from cell y to cell x. A link in state 0 is considered to be high-resistant, or non-conductive, and link in state 1 low resistant, or conductive. A link-state \(l^t_{xy}\) is updated depending on states of cells x and y at time step t: \(l^t_{xy} = f(x^t, y^t)\). Resting state gives little indication of cell’s previous history, therefore we will consider only non-resting cells contributing to a link state updates. When cells x and y are in the same state (bother cells are in state + or both are in state −) no ’current’ can flow between the cells, therefore scenarios x ^t = y ^t are not taken into account.

Andrew Adamatzky

Backmatter

Titel: Reaction-Diffusion Automata: Phenomenology, Localisations, Computation
verfasst von: Andrew Adamatzky
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-31078-2
Print ISBN: 978-3-642-31077-5
DOI: https://doi.org/10.1007/978-3-642-31078-2