Invited talks | Full papers | Exploratory papers
Invited Talks
Nicolas Schabanel
Oritatami systems: a computational model for co-transcriptional folding
The function of biomolecules is mostly driven by their shape, which is the result of folding sequences upon themselves. Predicting the outcome of this process has long been an important and hard problem in computer science. However, in some cases, most commonly in RNA, folding happens co-transcriptionally, i.e. following a greedy process during production of the molecule. And indeed, recent experiments (2014) demonstrated how RNA engineering allows recently to fold co-transcriptionally into prescribed nano-shapes at life-compatible temperature as opposed to DNA technology that requires heating the molecules up to high temperatures (≥ 70°C) before letting them cool down.
With the new model introduced in this presentation, our goal is twofold: first, explore the engineering possibilities of co-transcriptional folding; then, to understand the complexity of sequence operations, and the computational processes which lead to the creation of complex molecular networks.
More precisely, we will present how one can program co-transcriptional folding to implement arbitrary Turing calculation, yielding some intuition on how computation might work in nature. We will also show that designing a given molecule is NP-hard but fixed-parameter tractable with respect to the length of the desired molecule.
This is joint work with Cody Geary, Pierre-Étienne Meunier and Shinnosuke Seki.
Guillaume Theyssier
Propagation, diffusion and randomization in cellular automata
A large part of the study of cellular automata dynamics consists in comparing pairs of configurations and their orbits. Here we focus on pairs of configurations having a finite number of differences (diamonds) like in the celebrated Garden-of-Eden theorem. First, we show that it allows to study expansive-like phenomena where classical notions of chaotic behavior like positive expansivity or strong transitivity don't apply (in reversible CAs for instance). Second, we establish that for a large class of linear CA, diffusion of diamonds is equivalent to randomization (a large class of probability measures converge weakly towards the uniform measure under the action of the CA). Both properties are also equivalent to the absence of gliders in the CA. Finally, we give examples of reversible linear CAs that are strong randomizers (the convergence towards the uniform measure is simple and not only in Cesaro mean). This strong behavior is however provably impossible with linear CA having commuting coefficients (e.g. linear CA over cyclic groups).
Tommaso Toffoli
What automata can provide a medium for life?
Hadn't this question already been answered? We all know about computation-universal Turing Machines. And we know that any such machine can simulate a space-time dynamics not unlike von Neumann's cellular automaton, which is computation- and construction-universal and among other things can play host to self-replicating machines. And that self-replication sprinkled with a bit of randomness should inexorably lead to descent with variation, competition, and thence to evolution and all that.
And note that the state of the art has much advanced in the fifty years since. ``So?'' Enrico Fermi would have asked, ``Where is everybody?''
It turns out that life is by its very nature a marginal, fragile, and ephemeral kind of phenomenon. For a substrate or a ``culture medium'' to be able to support it, computation- and construction-universality are necessary---but by no means sufficient! Most automata (including, I suspect, Conway's very game of "life") will go through their entire life course without ever originating anything like life.
What questions, then, should we ask of a prospective medium---be it a Turing machine, a cellular automaton, or some other kind of automaton---that will probe its capabilities to originate and/or support some form of life?
Andrew Winslow
A Tour of DNA Tile Self-Assembly
In the 1990s, Ned Seeman and Erik Winfree developed a method for programming sets of short DNA strands to spontaneously assemble into desired nanoscale structures. Simultaneously, Winfree formalized these systems as the abstract DNA tile self-assembly model. In this model, square tiles attach edgewise via matching bonding sites to form polyomino-shaped structures. Since then, the study of both experimental and theoretical DNA tile self-assembly has grown tremendously. In this talk, we explore the theoretical half of this work. Starting with its roots in the Ph.D. thesis of Winfree, we trace the proliferation of models, problems, and techniques, ending with ongoing work to develop a "structural complexity theory for tile assembly.
Full Papers
Shigeki Akiyama and Katsunobu Imai
The corona limit of Penrose tilings is a regular decagon
We define and study the corona limit of a tiling, by investigating the signal propagations on cellular automata (CA) on tilings employing the simple growth CA. In particular, the corona limit of Penrose tilings is the regular decagon.
Sebastián Barbieri, Jarkko Kari and Ville Salo
We consider Turing machines as actions over configurations in $\Sigma^{\mathbb{Z}^d}$ which only change them locally around a marked position that can move and carry a particular state. In this setting we study the monoid of Turing machines and the group of reversible Turing machines. We also study two natural subgroups, namely the group of finite-state automata, which generalizes the topological full groups studied in the theory of orbit- equivalence, and the group of oblivious Turing machines whose movement is independent of tape contents, which generalizes lamplighter groups and has connections to the study of universal reversible logical gates. Our main results are that the group of Turing machines in one dimension is neither amenable nor residually finite, but is locally embeddable in finite groups, and that the torsion problem is decidable for finite-state automata in dimension one, but not in dimension two.The group of reversible Turing machines
Tom Besson and Jérôme Durand-Lose
Exact Discretization of 3-Speed Rational Signal Machines into Cellular Automata
Cellular Automata (CA) operate in discrete time and space whereas Signal Machines (SM) have been developed as a continuous idealization of CA capturing the key concept of signals/particles and collisions. Inside a Euclidean space, dimensionless signals move freely; collisions are instantaneous. Today’s issue is the automatic generation of a CA mimicking a given SM. On the one hand, many ad hoc manual conversions exist. On the other hand, some irrational or 4+-speed SM exhibit Zeno-like behaviors / space-time compression or rely on information being locally unbounded, both being incompatible with CA. This article provides a solution to automatically generate an exactly mimicking CA for a restricted class of SM: the ones that uses only three rational speeds, and rational initial positions. In these SM, signals are always contained inside a regular mesh. The discretization brings forth the corresponding discrete mesh. The simulation is valid on any infinite run and preserves the relative position of collisions.
Silvio Capobianco, Jarkko Kari and Siamak Taati
An “almost dual” to Gottschalk’s conjecture
We discuss cellular automata over arbitrary finitely generated groups. We call a cellular automaton post-surjective if for any pair of asymptotic configurations, every pre-image of one is asymptotic to a pre-image of the other. The well known dual concept is pre-injectivity: a cellular automaton is pre-injective if distinct asymptotic configurations have distinct images. We prove that pre-injective, post-surjective cellular automata are reversible. We then show that on sofic groups, where it is known that injective cellular automata are surjective, post-surjectivity implies pre-injectivity. As no non-sofic groups are currently known, we conjecture that this implication always holds. This mirrors Gottschalk’s conjecture that every injective cellular automaton is surjective.
Alonso Castillo-Ramirez and Maximilien Gadouleau
On Finite Monoids of Cellular Automata
For any group $G$ and set $A$, a cellular automaton over $G$ and $A$ is a transformation $\tau : A^G \to A^G$ defined via a finite neighbourhood $S \subseteq G$ (called a memory set of $\tau$) and a local function $\mu : A^S \to A$. In this paper, we assume that $G$ and $A$ are both finite and study various algebraic properties of the finite monoid $\mathrm{CA}(G,A)$ consisting of all cellular automata over $G$ and $A$. Let $\mathrm{ICA}(G;A)$ be the group of invertible cellular automata over $G$ and $A$. In the first part, using information on the conjugacy classes of subgroups of $G$, we give a detailed description of the structure of $\mathrm{ICA}(G;A)$ in terms of direct and wreath products. In the second part, we study generating sets of $\mathrm{CA}(G;A)$. In particular, we prove that $\mathrm{CA}(G,A)$ cannot be generated by cellular automata with small memory set, and, when $G$ is finite abelian, we determine the minimal size of a set $V \subseteq \mathrm{CA}(G;A)$ such that $\mathrm{CA}(G;A) = \langle \mathrm{ICA}(G;A) \cup V \rangle$.
Emilio Nicola Maria Cirillo, Francesca Romana Nardi and Cristian Spitoni
Sum of exit times in series of metastable states in Probabilistic Cellular Automata
Reversible Probabilistic Cellular Automata are a special class of automata whose stationary behavior is described by Gibbs–like measures. For those models the dynamics can be trapped for a very long time in states which are very different from the ones typical of stationarity. This phenomenon can be recasted in the framework of metastability theory which is typical of Statistical Mechanics. In this paper we consider a model presenting two not degenerate in energy metastable states which form a series, in the sense that, when the dynamics is started at one of them, before reaching stationarity, the system must necessarily visit the second one. We discuss a rule for combining the exit times from each of the metastable states.
Ronaldo de Castro Corrêa and Pedro P.B. de Oliveira
Partial reversibility of one-dimensional cellular automata
Reversibility is the property of very special cellular automata rules by which any path traversed in the configuration space can be traversed back by its inverse rule. Expanding this context, the notion of partial reversibility has been previously proposed in the literature, as an attempt to refer to rules as being more or less reversible than others, since some of the paths of non-reversible rules could be traversed back. The approach was couched in terms of a characterisation of the rule’s pre-image pattern, that is, the number of pre-images of a rule for all configurations up to a given size, and their relative lexicographical ordering used to classify the rules in terms of their relative partial reversibility. Here, we reassess the original definition and define a measure that represents the reversibility degree of the rules, also based on their pre-image patterns, but now relying on the probability of correctly reverting each possible cyclic, finite length configuration, up to a maximum size. As a consequence, it becomes possible to look at partial reversibility in absolute terms, and not relatively to other rules, as well to infer the reversibility degrees for arbitrary lattice sizes, even in its limit to infinity. All the discussions are restricted to the elementary space, but are also applicable to any one-dimensional rule space.
Nazim Fatès, Irène Marcovici and Siamak Taati
Two-dimensional traffic rules and the density classification problem
The density classification problem is the computational problem of finding the majority in a given array of votes, in a distributed fashion. It is known that no cellular automaton rule with binary alphabet can solve the density classification problem. On the other hand, it was shown that a probabilistic mixture of the traffic rule and the majority rule solves the one-dimensional problem correctly with a probability arbitrarily close to one. We investigate the possibility of a similar approach in two dimensions. We show that in two dimensions, the particle spacing problem, which is solved in one dimension by the traffic rule, has no cellular automaton solution. However, we propose exact and randomized solutions via interacting particle systems. We assess the performance of our models using numeric simulations.
Anaël Grandjean
Constant acceleration theorem for extended von Neumann Neighbourhoods
We study 2-dimensional cellular automata as language recognizers. We are looking for closure properties, similar to the one existing in one dimension. Some results are already known for the most used neighbourhoods, however many problems remain open concerning more general neighbourhoods. In this paper we provide a construction to prove a constant acceleration theorem for extended von Neumann neighbourhoods. We then use this theorem and some classical tools to prove the equivalence of those neighbourhoods, considering the set of languages recognizable in real time.
Augusto Modanese and Thomas Worsch
Shrinking and Expanding Cellular Automata
Inspired by shrinking cellular automata (SCA), we investigate another variant of the classical one-dimensional cellular automaton: the shrinking and expanding cellular automaton (SXCA). In addition to the capability to delete some cells as in SCA, an SXCA can also create new cells between already existing ones. It is shown that there are reasonably close (polynomial) relations between the time complexity of SXCA and the space and time complexity of Turing machines and alternating Turing machines respectively. As a consequence the class of problems decidable in polynomial time by SXCA coincides with PSPACE.
Kenichi Morita
An 8-State Simple Reversible Triangular Cellular Automaton That Exhibits Complex Behavior
A three-neighbor triangular partitioned cellular automaton (TPCA) is a CA whose cell is triangular-shaped and divided into three parts. The next state of a cell is determined by the three adjacent parts of its neighbor cells. The framework of TPCA makes it easy to design reversible triangular CAs. Among them, isotropic 8-state (i.e., each part has two states) TPCAs, which are called elementary TPCAs (ETPCAs), are extremely simple, since each of their local transition functions is described by only four local rules. In this paper, we investigate a specific reversible ETPCA $T_{0347}$ , where 0347 is its identification number in the class of 256 ETPCAs. In spite of the simplicity of the local function and the constraint of reversibility, evolutions of configurations in $T_{0347}$ have very rich varieties, and look like those in the Game-of-Life CA to some extent. In particular, a “glider” and “glider guns” exist in $T_{0347}$. Furthermore, using gliders to represent signals, we can implement universal reversible logic gates in it. By this, computational universality of $T_{0347}$ is derived.
Simon Wacker
Cellular Automata on Group Sets and the Uniform Curtis-Hedlund-Lyndon Theorem
We introduce cellular automata whose cell spaces are left homogeneous spaces and prove a uniform as well as a topological variant of the Curtis-Hedlund-Lyndon theorem. Examples of left homogeneous spaces are spheres, Euclidean spaces, as well as hyperbolic spaces acted on by isometries; vertex-transitive graphs, in particular, Cayley graphs, acted on by automorphisms; groups acting on themselves by multiplication; and integer lattices acted on by translations.
Exploratory papers
Roderick Edwards and Aude Maignan
DEM-Systems: a new type of adaptive system
A generic adaptive network called a DEM-system is presented. Deeply influenced by cellular automata (CA) and L-Systems, it has the structural flexibility of an L-system but can expand to higher dimensions and inherits algebraic properties of CA. The behavior of DEM- systems are discussed here in the case of a linear ring or chain. For the additive case, a partial partition into three finiteness classes is given. Interesting behaviors, such as reproduction, are exhibited.
Jeremias Epperlein
Conjugacy of Cellular Automata on Tori and Surjectivity
Cellular automata have many finite subsystems given by their restriction to spatially periodic points with a fixed period. To our knowledge there has been up to now no systematic study of properties that can be derived from the dynamics of these subsystems. We call two cellular automata conjugate on a torus $\mathbb{Z}^d/v\mathbb{Z}^d$, if their restrictions to $\mathbb{Z}^d/v\mathbb{Z}^d$ are conjugate. In particular we consider them to be equivalent if they are conjugate on all tori and ask which properties are invariant under this equivalence. It is proved that surjectivity is such a property. This is straight forward in dimension one, in higher dimensions, however, we show this by investigating the Shannon entropy of the image of the uniform measure on configurations on the tori.
Eric Goles, Diego Maldonado, Pedro Montealegre-Barba and Nicolas Ollinger
Two State Totalistic Freezing Cellular Automata and their Complexity
We study the computational complexity of a family of simple two-dimensional, two-state freezing CA. In such family of CA, sites in state 0 change to state 1 depending only on the sum of the states of their neighbors, while sites in state 1 remain always in that state. The complexity of a CA is the one of the problem consisting in the prediction of the state of a site in a given time step. We show that in this family of 32 local rules, is possible to find cases with P -Complete, N C, and constant time complexity.
Urban Larsson
Hopeful windows and fractals in cellular automata and combinatorial games
This paper studies 2-player impartial combinatorial games, where the outcomes correspond to updates of cellular automata (CA) which generalize Wolfram’s elementary rule 60 and rule 110 (Cook 2004). The games extend the class of triangle placing games (Larsson 2013) where at each stage of the game the previous player has the option to block certain hopeful moves of the next player. We also study fractals and partial convergence in a subclass of the CA.
Luca Mariot, Enrico Formenti and Alberto Leporati
Constructing Orthogonal Latin Squares from Linear Cellular Automata
We undertake an investigation of combinatorial designs engendered by cellular automata (CA), focusing in particular on orthogonal Latin squares and orthogonal arrays. The motivation is of cryptographic nature. Indeed, we consider the problem of employing CA to define threshold secret sharing schemes via orthogonal Latin squares. We first show how to generate Latin squares through bipermutive CA. Then, using a characterization based on Sylvester matrices, we prove that two linear CA induce a pair of orthogonal Latin squares if and only if the polynomials associated to their local rules are relatively prime.
Genaro Martinez and Andrew Adamatzky
Circular computing with rule 110
We show how computing operations with the cyclic tag system can be implemented in elementary cellular automaton rule 110 based-collision of gliders via a circular machine with a finite number of cells for each of the operation.
Dalibor Štys, Kryštof Štys, Anna Zhyrova and Renata Rychtáriková
Optimal noise in the hodgepodge machine simulation of the Belousov-Zhabotinsky reaction
One of the simplest multilevel cellular automata – the hodgepodge machine – was modified to best match the chemical trajectory observed in the Belousov-Zhabotinsky reaction. Noise introduces water- sheding of the central regular pattern into the circular target pattern. This article analyzes influences of the neighborhood and internal excitation kinds of noise. We have found that configurations of ignition points, which give circular waves – target patterns, occur only in the interval of the neighborhood excitation noise from 30% to 34% and at the internal excitation noise of 12%. Noisy hodgepodge machine with these parameters is the best approximation to the experimental Belousov-Zhabotinsky reaction.