On the iota-delta function: a link between cellular automata and partial differential equations for modeling advection–dispersion from a constant source

Abstract

Describing complex phenomena by means of cellular automata (CAs) has shown to be a very effective approach in pure and applied sciences. Most of the applications, however, rely on multidimensional CAs. For example, lattice gas CAs and lattice Boltzmann methods are widely used to simulate fluid flow and both share features with two-dimensional CAs. One-dimensional CAs, on the other hand, seem to have been neglected for modeling physical phenomena. In the present paper, we demonstrate that some one-dimensional CAs are equivalent to a stable linear finite difference scheme used to solve advection–diffusion partial differential equations (PDEs) by relying on the so-called iota-delta representation. Consequently, this work shows an important link between continuous and discrete models in general, and PDEs and CAs more in particular.

1 Introduction

Complexity inevitably arises in nature [1]. Possible ways of addressing and understanding this are of great interest to the scientific community [2]. Moreover, as the amount of available computing power grew during the past three decades, the study of dynamical systems has intensified considerably. Amongst other things, the pioneering work by John von Neumann and Stanislaw Ulam shows that a special class of the latter, so-called cellular automata (CAs), can give rise to rich and physically justifiable behavior [1]. This was further confirmed by Wolfram [3], who established the basis for the study of one-dimensional CAs [1].

The applicability of CAs to describe physical systems quickly drew attention of scientists in the 1970s and early 1980s, culminating in the development of the HPP model [4]. Yet, this model lacked Galilean invariance, and presented statistical noise, which ultimately led to lack of isotropy [5].

Some works built upon and improved the HPP model and about 10 years later the FHP model was put forward by Frich et al. [6]. Both the HPP and FHP models belong to the class of the so-called lattice gas CAs (LGCAs). Independently, Wolfram [7] proposed another approach to avoid some of the shortcomings of the HPP model. Still, few problems could not be overcome by relying on the FHP model (such as noise), which ultimately led to the development of the Lattice Boltzmann method [5]. In an early work, Frisch et al. [8] already had implemented Boltzmann distributions to evaluate the viscosity of LGCA schemes. The noise related to the Boolean nature of LGCAs, however, remained an issue. McNamara and Zanetti [9] presented for the first time the Lattice Boltzmann method as an autonomous numerical scheme to conduct hydrodynamical simulations. These automata-related approaches are models whose interaction rules mimic fluid-like behavior. When spatially averaging the evolved configurations, the obtained overall behavior should approach the outcome one gets by relying upon the Navier–Stokes equations.

Some insights into the usage of 1D CAs to model physical, biological and computational phenomena have been discussed by, amongst others, Wolfram [1] Ozelim et al. [10], Wuensche and Lesser [11], Chua [12–16] and Redeker et al. [17]. Still, despite the recurrent discussion on the topic [18–20], no generally valid relation between PDEs and CAs has been established. In the present paper, this issue is addressed for what concerns advection–dispersion from a constant source.

In Sect. 2, elementary cellular automata (ECAs) are briefly reviewed, while the formalism of the so-called iota-delta representation of ECAs is introduced in Sect. 3. Section 4 presents the basic notions on the considered advection–dispersion phenomenon and its description by means of a PDE and Sect. 5 shows how the iota-delta representation of ECAs can be used to establish a link between ECAs and the governing PDE.

2 Elementary cellular automata (ECAs)

A comprehensive study of ECAs can be found in [1] and [12–16]. In short, ECAs consist of a one-dimensional array of cells $C_{i}$, each of them bearing one out of two states, namely 0 or 1. At discrete time steps a predefined transition function is applied to each of the cells synchronously to compute their states at the next time step. Essentially, the state of a given cell $\hbox {C}_{i}$ at the next time steps $k+1$ is determined by its own and the one of its left $C_{i}$ and right $C_{i+1}$, neighbors at the previous time step k [1]. So, denoting the state of cell $C_{i}$ at time step k as s$(C_{i}, k)$, we may write

$$\begin{aligned} s(C_{i} ,k+1)=f\left[ {s(C_{i-1} ,k),s(C_i ,k),s(C_{i+1} ,k)} \right] \end{aligned}$$

(1)

In this way, an ECA can be characterized by a so-called rule icon (Fig. 1) and it is clear that 256 different transition functions can be listed in total. The enumeration scheme developed by Wolfram considers the outputs of the transition functions as coefficients in the decomposition of a given number base 2 to determine the corresponding rule number [1]. In the case of the rule depicted in Fig. 1, the rule number is given as $0\times 2^{7}+0\times 2^{6}+0\times 2^{5}+1\times 2^{4}+1\times 2^{3}+1\times 2^{2}+1\times 2^{1}+0\times 2^{0}=30$.

Fig. 1

Evolution or ECA rule 30

3 The iota-delta function representation of ECAs

In a recent paper, Ozelim et al. [21] propose a new general representation for ECAs, the so-called iota-delta representation. This was done using a homonymous function defined in [21]: the iota-delta function. The idea behind the iota-delta function is quite simple. Starting from the fact that the transition function of ECA rule 90 is given by

$$\begin{aligned} s(C_{i} ,k+1)=\bmod \left[ {s(C_{i-1} ,k)+s(C_{i+1} ,k);2} \right] , \end{aligned}$$

(2)

which is equivalent to the XOR operation with s$(C_{i},k)$ and s$(C_{i+1},k)$, a generalization can be conceived by introducing three constants $\alpha _j =\left\{ {0,1} \right\}$ for $j=1,2,3$. More precisely, a more general representation of ECA transition functions is given by [21]:

$$\begin{aligned} s(C_{i} ,k+1)=\bmod \left[ {\alpha _{1} s(C_{i-1} ,k)+\alpha _{2} s(C_{i} ,k)+\alpha _{3} s(C_{i+1} ,k);2} \right] . \end{aligned}$$

(3)

Since the constants $\alpha _{j}$can only be 0 and 1 only a limited number of rules can be described by Eq. (3), namely ECA rules 0, 60, 90, 102, 150, 170, 204 and 240 [21]. Equation (3) also presents a “parity” problem: the odd rules, according to Wolfram’s enumeration scheme, can never be represented because in that case

$$\begin{aligned} s(C_{k} ,i+1)=\bmod \left[ {\alpha _{1} 0+\alpha _{2} 0+\alpha _{3} 0;2} \right] =0;\quad \forall \alpha _{j} ,j=1,2,3. \end{aligned}$$

(4)

In order to overcome this issue, the representation in Eq. (3) may be improved by considering a fourth constant [21]:

$$\begin{aligned} s(C_{i} ,k+1)=\bmod \left[ {\alpha _{1} s(C_{i-1} ,k)+\alpha _{2} s(C_{i} ,k)+\alpha _{3} s(C_{i+1} ,k)+\alpha _{4} ;2} \right] . \end{aligned}$$

(5)

Using the 16 possible combinations of binary coefficients, 16 ECA evolution rules can be defined [21]. In order to represent even more ECA rules, Ozelim et al. [21] propose to wrap multiple modular operations:

$$\begin{aligned} s(C_{i} ,k+1){=}\bmod \left[ {\bmod \left[ {\alpha _{1} s(C_{i-1} ,k){+}\alpha _{2} s(C_{i} ,k){+}\alpha _{3} s(C_{i+1} ,k){+}\alpha _{4} ;3}\right] ;2} \right] .\nonumber \\ \end{aligned}$$

(6)

The constants in Eq. (6) can now take three values instead of 2, resulting in a total of 81 combinations. Using Eq. (6) it is now possible to represent 53 ECA rules, taking into account the fact that some rules are represented by different sets of constants [21]. To represent even more ECA rules, the wrapping has to be done with higher congruence moduli. This was made possible by conceiving the so-called iota-delta function $\delta :\mathrm{C}\rightarrow \left\{ {a+bi;a,b\in \left[ {0,p_{m} )} \right. } \right\}$, which is defined mathematically as [21]:

$$\begin{aligned} \iota \delta _{n}^{m} (x)= & {} \bmod [\bmod [\ldots \bmod [\bmod [x,p_{m} ],p_{m-1} ],\ldots ,p_j ],n],\nonumber \\ m\ge & {} j;\;m,n\in \mathrm{Z}_{+} ;\;x\in \mathrm{C};\;j=\pi (n)+1, \end{aligned}$$

(7)

in which m and n are parameters of the iota-delta function, $p_{m}$ is the m-th prime number and $\pi (n)$ stands for the prime counting function that gives the number of primes less than or equal to n.

According to Ozelim et al. [21] every ECA can be represented by:

$$\begin{aligned} s(C_{i} ,k+1)=\iota {\delta _{2}^{5}} \left( {\alpha _{1} s(C_{i-1} ,k)+\alpha _{2} s(C_{i} ,k)+\alpha _{3} s(C_{i+1} ,k)+\alpha _{4} } \right) , \end{aligned}$$

(8)

where $\alpha _{j} =\left\{ {\left. r \right| r\le p_{5} -1,r\in \mathbb {Z}_+ } \right\}$ for $j=1,\ldots ,4$.

Hence, every ECA can be represented by means of a quadruple $\{\alpha _{1} ,\alpha _{2} ,\alpha _{3} ,\alpha _{4} \}$. The list of quadruples for the 88 minimal ECA rules can be found in Table 1.

Table 1 Iota-delta representation of the 88 minimal ECA rules with $m = 5$ and $n = 2$

Since different quadruples can encode the same ECA rule, an ECA rule can have more than one iota-delta function representation. For example, ECA rule 150 can be represented by $s\left( {C_{i} ,k+1} \right) =\iota {\delta _{2}^{5}} \left( {s\left( {C_{i-1} ,k} \right) +s\left( {C_{i} ,k} \right) +s\left( {C_{i+1} ,k} \right) +3} \right)$ and $s\left( {C_{i} ,k+1} \right) =\iota \delta _2^3 \left( {s\left( {C_{i-1} ,k} \right) +s\left( {C_{i} ,k} \right) +4s\left( {C_{i+1} ,k} \right) } \right)$. Now, one may look for a representation where for every odd rule it holds that $\alpha _{4} =1$, whereas for every even rule it holds that $\alpha _{4} =0$. This can be achieved by increasing the possible values of the other constants, which implies wrapping more congruence moduli around, such as increasing the parameter m in the iota-delta function representation. Thus, in this case, the minimal function to be used to represent every ECA is $\iota \delta _2^6 (x)$. Table 2 presents the iota-delta representation of the 88 minimal ECA rules for which it holds that $\alpha _{4} =1$for every odd rule, whereas for every even rule $\alpha _{4} =0$.

Table 2 Iota-delta representation of the 88 minimal ECA rules

For example, based on Table 1, ECA rule 30 rule can be written as:

$$\begin{aligned} s(C_{i} ,k+1)=\iota {\delta _{2}^{5}} \left( {s(C_{i-1} ,k)+4s(C_{i} ,k)+4s(C_{i+1} ,k)} \right) . \end{aligned}$$

(9)

For what concerns the iota-delta function $\iota {\delta _{2}^{5}} \left( x \right)$, it can be verified that this is a periodic function with period 11, being the largest last prime in its definition and the period of the outmost modular function. Its behavior in one period is shown in Fig. 2.

Fig. 2

The graph of $\iota {\delta _{2}^{5}} \left( x \right)$

In the subsequent part of this paper, the iota-delta representation will be used to link ECAs to the PDE describing the advection–dispersion phenomenon, but first we will discuss advection–dispersion phenomena and how finite difference methods (FDMs) for solving the governing equations can be retrieved from ECAs.

4 Advection–dispersion and finite differences schemes

Finite differences are used to numerically approximate PDEs by turning them into difference equations, which can then be solved to arrive at an approximate solution of the governing PDE [22]. In order to illustrate the applicability of the methodology hereby presented, the advection–dispersion equation is considered. This equation describes, for example, the solute flow in a porous medium.

Let the equation that describes the concentration $c(\hbox {x,t})$ of a given solute flowing in a porous medium at some location in space and instance in time be given by [23]:

$$\begin{aligned} \frac{\partial c}{\partial t}=D_{x} \frac{\partial ^{2}c}{\partial x}-v_{x} \frac{\partial c}{\partial x}, \end{aligned}$$

(10)

in which $D_{x} [\hbox {L}^{2}/\hbox {T}]$ is the hydrodynamic dispersivity of the medium and $v_{x} [\hbox {L}/\hbox {T}]$ is the mean velocity of the interstitial fluid.

Now, let us rely on the forward and backward difference approximation in time and space, respectively, for the first-order derivative, while using a central difference approximation for discretizing the second-order derivative in space [24]. Hence, by considering a rectangular mesh with grid spacings ${\Delta t}$ and ${\Delta x}$ Eq. (10) can be approximated by

$$\begin{aligned} \frac{c(x,t+\Delta t)-c(x,t)}{\Delta t}= & {} D_{x} \frac{c(x+\Delta x,t)-2c(x,t)+c(x-\Delta x,t)}{\Delta x^{2}}\nonumber \\&\quad -v_{x}\frac{c(x,t)-c(x-\Delta x,t)}{\Delta x}. \end{aligned}$$

(11)

In order to simplify the notation and clarify the link between the FDM and CAs, let us introduce i to index the finite difference nodes along the x axis, and k to index the nodes along the t axis. Further, let us introduce the following:

$$\begin{aligned} \frac{D_{x} \Delta t}{\Delta x^{2}}= & {} N,\end{aligned}$$

(12)

$$\begin{aligned} \frac{v_{x} \Delta t}{\Delta x}= & {} C_{r}, \end{aligned}$$

(13)

with N and $C_{r}$ being the Neumann and Courant numbers, respectively. By denoting $c\left( {i\Delta x,k\Delta t} \right)$ as $c_{i}^k$, Eq. (11) can be reformulated as

$$\begin{aligned} c_{i}^{k+1} =\left( {N+C_{r} } \right) c_{i-1}^{k} +\left( {1-C_{r} -2N} \right) c_{i}^{k} +Nc_{i+1}^{k}. \end{aligned}$$

(14)

Relying upon the Courant, Fredrich and Levy condition [24], it may be concluded that the introduced FDM scheme is convergent if

$$\begin{aligned} 2N+C_{r} \le 1. \end{aligned}$$

(15)

The similarity between Eqs. (8) and (14) is remarkable, but a clear conceptual difference is present: while the former describes the evolution of a discrete-state system, the latter describes the dynamics of a continuous-state system. The main question is how to relate both.

5 ECAs for advection–dispersion phenomena

In order to compare the dynamics evolved by ECAs to the one evolved by PDEs for one-dimensional advection–dispersion phenomenon, one first has to set the proper boundary and initial conditions. In the present paper, a semi-infinite domain is chosen. The concentration of a given substance is kept constant at the left side of the spatial domain, i.e. a so-called Dirichlet boundary condition, while it is initially 0 elsewhere. Moreover, the concentrations are scaled with respect to a certain maximum concentration, namely the one that is present at the leftmost side of the spatial domain. Consequently, the concentration at the origin is always 1, while it lies in the unit interval elsewhere. Figure 3 shows the first three configurations that are obtained by applying Eq. (14) iteratively from the imposed initial and boundary conditions. It is easy to see that the unknowns in the consecutive configurations are given by

$$\begin{aligned} \left\{ {{\begin{array}{l} {A=N+C_{r} } \\ {B=(N+C_{r} )\left( {2 - C_{r} - 2N} \right) } \\ {C=\left( {N+C_{r} } \right) ^{2}} \\ \end{array} }} \right. \end{aligned}$$

(16)

Fig. 3

Evolution of the FDM scheme applied to a constant source advection–dispersion phenomenon after two iterations

It should be recalled that A, B and C are real numbers as they result from a PDE that is built upon a continuous state domain.

The next step is to link the ECA evolution from the same initial configuration as the one given at the top of Fig. 3 to the one obtained with the FDM. First of all, Eq. (8) should be modified in such a way that it can lead to the values obtained using the FDM, i.e. the values given by system (16).

In essence, the iota-delta representation of ECAs rules enables one to mathematically relate states in previous time steps k to future time steps $k +1$, similar to the representations proposed others (see [1] for a review on this topic), but the key advantages of the iota-delta function is that this relation is done in terms of a linear combination of the cell states in the previous time steps. It is clear from Eq. (9), for example, that the evolution function can be split up into two parts: the linear dependence on the cell states and the nonlinear wrapping function (the iota-delta function).

Equation (14), which represents a FDM for the advection–dispersion PDE, can be interpreted as an evolution rule in which the value of the cell in the next time step (concentration in this case) is given by a linear combination of cell values’ in previous time steps. This is quite similar to the iota-delta representation of the ECA rules, with the only difference that this one involves the iota-delta function “wrapping”. Thus, to relate both evolution rules, it is clear that one has to remove the nonlinear part of the iota-delta representation. In other words, one has to look for ways to get $\iota {\delta _{2}^{m}} (x)=x$ for every m.

On the basis of Fig. 2, it is clear that if the arguments of the iota-delta function are lower than 2, the identity function is retrieved. Hence, it is key to make sure that the argument of the iota-delta function is always less than 2 in order to link the FDM and ECAs. This can be achieved by two procedures: linear scaling the ECA rules by a factor S and changing the initial condition from 1 to $\Omega$. From the definition of the iota-delta function it follows that $\iota {\delta _{2}^{m}} (x)<2$ for every m. Thus, by making S less than 1, one guarantees that in next time steps the outputs will be less than 2, while choosing $\Omega$ lower than 1 guarantees that after the first time step, the argument will also be less than 2.

Mathematically, by linearly scaling the right-hand side of Eq. (8) by a non-zero factor S, the corresponding ECA transition function becomes

$$\begin{aligned} s(C_{i} ,k+1)=S\iota {\delta _{2}^{5}} \left( {\alpha _{1} s(C_{i-1} ,k)+\alpha _{2} s(C_{i} ,k)+\alpha _{3} s(C_{i+1} ,k)+\alpha _{4} } \right) . \end{aligned}$$

(17)

When Eq. (17) is applied to the initial configuration in the top row of Fig. 3, the subsequent configurations still obey the constant source hypothesis. Further, as discussed previously, in order to guarantee that after the first time step the arguments of the iota-delta function will be less than 2, one has to set the concentration in the source to $\Omega$ (Fig. 4).

Fig. 4

Evolution of the ECA updating scheme applied to a constant source advection–dispersion phenomenon

Figure 4 shows the first two configurations that are obtained by applying Eq. (17) iteratively, where one obtains for the unknowns $A', B'$ and $C'$:

$$\begin{aligned} \left\{ {{\begin{array}{l} {A^{\prime }=S\iota {\delta _{2}^{5}} \left( {\alpha _{1} \Omega +\alpha _{4} } \right) } \\ {B^{\prime }=S\iota {\delta _{2}^{5}} \left( {\alpha _{1} \Omega +\alpha _{2} S\iota {\delta _{2}^{5}} \left( {\alpha _{1} \Omega +\alpha _{4} } \right) +\alpha _{4} } \right) } \\ {C^{\prime }=S\iota {\delta _{2}^{5}} \left( {\alpha _{1} S\iota {\delta _{2}^{5}} \left( {\alpha _{1} \Omega +\alpha _{4} } \right) +\alpha _{4} } \right) } \\ \end{array} }} \right. . \end{aligned}$$

(18)

Starting from the imposed initial and boundary conditions, it is clear that after a large number of iterations, the cells close to the origin have values that are very close to 1 or $\Omega$, when relying on the FDM and ECA, respectively. This is the so-called steady-state solution of the involved advection–dispersion problem. Hence, after a sufficient number of time steps, the configuration shown in Fig. 5 should be present near the origin.

Fig. 5

Steady-state condition that will be obtained after a sufficient number of time steps using the FDM (left) and ECA (right)

Once a configuration with a sequence of 1s is obtained, it will persist in the case of the FDM because the sum of the coefficients which multiply the values of the cells in Eq. (14) is equal to 1. For the ECA, on the other hand, the following equation is obtained for the evolution from a configuration containing only $\Omega$’s (Fig. 5):

$$\begin{aligned} \Omega =S\iota {\delta _{2}^{5}} \left( {\Omega \left( {\alpha _{1} +\alpha _{2} +\alpha _{3} } \right) +\alpha _{4} } \right) . \end{aligned}$$

(19)

Reconsidering Fig. 2 and the discussions regarding the argument of the iota-delta function, it is clear that the argument of the iota-delta function in Eq. (19) has to be smaller than 2, since then it holds that $\iota {\delta _{2}^{5}} (x)=x$. For that reason, the following condition should hold:

$$\begin{aligned} \Omega <\frac{2-\alpha _{4} }{\left( {\alpha _{1} +\alpha _{2} +\alpha _{3} } \right) }. \end{aligned}$$

(20)

Given that it is possible to express every odd rule with $\alpha _{4} =1$ and every even rule with $\alpha _{4} =0$, the right-hand side of Eq. (20) is positive for every ECA, so it reduces to

$$\begin{aligned} \Omega <\frac{1}{\left( {\alpha _{1} +\alpha _{2} +\alpha _{3} } \right) }. \end{aligned}$$

(21)

For simplicity, one can choose $\Omega =\left[ {2\left( {\alpha _{1} +\alpha _{2} +\alpha _{3} } \right) } \right] ^{-1}$, though any other value that satisfies Eq. (20) may be used as well. Continuing with this choice, Eq. (19) finally yields

$$\begin{aligned} S=\frac{1}{\left( {\alpha _{1} +\alpha _{2} +\alpha _{1} } \right) \left( {1+2\alpha _{4} } \right) } \end{aligned}$$

(22)

Since every odd rule is related to an even one by color inversion, one may restrict attention to the even rules only, such that we may consider $\alpha _{4} =0$.

In order to link the evolutions in Figs. 2 and 3, one has to divide the states of the cells in the latter by $\Omega$. This way, the following system of equations arises:

$$\begin{aligned} \left\{ {\begin{array}{l} \displaystyle 2\left( {\alpha _{1} +\alpha _{2} +\alpha _{3} } \right) \frac{\iota {\delta _{2}^{5}} \left( {\frac{\alpha _{1} }{2\left( {\alpha _{1} +\alpha _{2} +\alpha _{3} } \right) }} \right) }{\left( {\alpha _{1} +\alpha _{2} +\alpha _{3} } \right) }=N+C_{r} \\ \displaystyle 2\left( {\alpha _{1} +\alpha _{2} +\alpha _{3} } \right) \frac{\iota {\delta _{2}^{5}} \left( {\frac{1}{\left( {\alpha _{1} +\alpha _{2} +\alpha _{3} } \right) }\left[ {\frac{\alpha _{1} }{2}+\alpha _{2} \iota {\delta _{2}^{5}} \left( {\frac{\alpha _{1} }{2\left( {\alpha _{1} +\alpha _{2} +\alpha _{3} } \right) }} \right) } \right] } \right) }{\left( {\alpha _{1} +\alpha _{2} +\alpha _{3} } \right) }=\left( {N+C_{r} } \right) \left( {2-C_{r} -2N} \right) \\ \displaystyle \frac{1}{\left( {\alpha _{1} +\alpha _{2} +\alpha _{3} } \right) \left( {1+2\alpha _{4} } \right) }\iota {\delta _{2}^{5}} \left( {\frac{\alpha _{1} }{\left( {\alpha _{1} +\alpha _{2} +\alpha _{3} } \right) \left( {1+2\alpha _{4} } \right) }\iota {\delta _{2}^{5}} \left( {\frac{\alpha _{1} }{2\left( {\alpha _{1} +\alpha _{2}+\alpha _{3} } \right) }{+}\alpha _{4} } \right) {+}\alpha _{4} } \right) \\ \quad \;=\left( {N+C_{r} } \right) ^{2} \\ \end{array}} \right. \nonumber \\ \end{aligned}$$

(23)

It is easy to see that the arguments of the iota delta functions in system (23) are all less than 2, such that they are equivalent to identity functions (Fig. 2). Thus, the solution of system (23) is:

$$\begin{aligned} \left\{ {\begin{array}{l} N=\frac{\alpha _{3} }{\left( {\alpha _{1} +\alpha _{2} +\alpha _{3} } \right) } \\ C_{r} =\frac{\alpha _{1} -\alpha _{3} }{\left( {\alpha _{1} +\alpha _{2} +\alpha _{3} } \right) } \\ \end{array}} \right. , \end{aligned}$$

(24)

which gives a physical meaning to ECAs rules. By choosing rules that obey system (24) and its physical constraints, an advection–dispersion phenomena characterized by a certain set of Neumann and Courant numbers may be associated with an ECA. The latter can then be used to mimic advection–dispersion phenomena at stake.

It is interesting to check the stability of the ECA scheme by means of Eq. (15). This way, the CFL condition implies

$$\begin{aligned} 2N+C_{r}= & {} \frac{2\alpha _{3} }{\left( {\alpha _{1} +\alpha _{2} +\alpha _{3} } \right) }+\frac{\alpha _{1} -\alpha _{3} }{\left( {\alpha _{1} +\alpha _{2} +\alpha _{3} } \right) }\nonumber \\= & {} \frac{\alpha _{1} +\alpha _{3} }{\left( {\alpha _{1} +\alpha _{2} +\alpha _{3} } \right) }\le 1,\quad \forall \alpha _j ,\quad j=1,2,3. \end{aligned}$$

(25)

This shows that the ECA schemes are always stable, in addition to the fact that they give the same results as the FDM. The latter is illustrated in Fig. 6 for ECA rule 62 that mimics an advection–dispersion phenomenon for which $N=C_{r} = 0.2$.

For ECA rule 62, we infer from Table 2 that $\{\alpha _{1} ,\alpha _{2} ,\alpha _{3} ,\alpha _{4} \}=\{8,8,4,0\}$. Figure 6a shows the configuration evolved by the corresponding iota-delta function starting from a single black cell at the LHS of the spatial domain. The next step involves a linear scaling of the transition function by S, where the latter can be found using Eq. (22), and yields S = 0.05. Figure 6b depicts the application of the scaled transition function starting from the same initial and boundary conditions as in Fig. 6a. At this point, we have to choose a value for $\Omega$ that fulfills the condition given by Eq. (21). Here, we choose $\Omega =0.025$ and Fig. 6c shows the corresponding evolution. Finally, all cell states are scaled back to meet the FDM the initial and boundary conditions for which the FDM is implemented, which is achieved by dividing all cell states $\Omega =0.025$ (Fig. 6d). Comparing Fig. 6d with Fig. 6e that depicts the evolution obtained using the governing FDM scheme with $N=C_{r}$ = 0.2 (cfr. Eq. (24)) it is clear that the obtained space–time diagrams are the same.

Fig. 6

Example of the proposed methodology: a space–time diagram of ECA rule 62; b after linear scaling of the transition function by S; c after changing the initial and boundary values to $\Omega$; d after dividing the cell states by $\Omega$ and e corresponding FDM results for $N=C_{r}$ = 0.2

The results presented here are easily generalized for larger FDM stencils. This is done by taking the dependency of $s(C_{i} ,k+1)$ with respect to more cells in Eq. (3).

Not only is the present methodology extendable to larger FDM stencils, but also to other partial differential equations. It is known that FDM schemes approximate derivatives by differences. These differences take into account the values of the dependent variables of the PDE in different spatial positions and/or time steps.

By imagining that the values of the dependent variables of PDEs are states in a grid, one can build a CA which will mimic the dependency on surrounding cells of the FDM scheme (even non-linear ones). This, together with the iota-delta formalism hereby proposed, will lead to a correspondence between PDEs and CAs.

It is worth noticing that the ideas presented above only apply to explicit FDM schemes. Implicit schemes still need to be investigated. The following proposition is established by the authors based on the discussions presented in this paper:

Proposition 1

Every PDE which can be approximated by an explicit FDM scheme will have a correspondent CA representation by means of the iota-delta formalism.

6 Conclusions

The usage of ECAs to describe physical phenomena has received much attention, but up to this day there is often no clear link between PDEs that are often used to describe such phenomena and their discrete counterparts. In this paper it is shown how an ECA can be constructed that mimics the advection–convection from a constant source and that leads to results that are comparable with those obtained using FDMs.