Reversibility, balance and expansivity of non-uniform cellular automata
Katariina Paturi · 2025
Read Reversibility, balance and expansivity of non-uniform cellular automata by Katariina Paturi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-06896.txt.
Introduction
Katariina Paturi studies non uniform cellular automata in a 2025 paper, based on the head title. Unlike classic automata, these systems apply several different local rules across the grid, set by a fixed rule layout. The question is which classic properties survive when that layout is required to be recurrent, repeating its pattern in a structured way.
A bijective system with a uniformly recurrent layout is shown to be reversible. Surjective systems with a recurrent layout, and bijective ones in general, are balanced. Examples separate nearby notions, one system has some calm points without being too regular, and another lacks calm points yet is not sensitive. Expansive systems are proven sensitive.
Catalog record
| CREATOR | Katariina Paturi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-06896
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Reversibility, balance and expansivity of non-uniform cellular automata Thanks: Supported by the Magnus Ehrnrooth foundation and the Research Council of Finland. Affiliation: University of Turku, Vesilinnantie 5, 20500 Turku, Finland Katariina Paturi Abstract Non-uniform cellular automata ( nuca ) are an extension of cellular automata ( ca ), which transform cells according to multiple different local rules. A nuca is defined by a configuration of local rules called a local rule distribution. We examine what properties of uniform ca can be recovered by restricting the rule distribution to be (uniformly) recurrent, focusing on only 1D nuca . We show that a bijective nuca with a uniformly recurrent rule distribution is reversible. We also show that if a nuca is surjective and has a recurrent rule distribution, or if it is bijective, then it is balanced. We present an example of a nuca which has a non-empty and non-residual set of equicontinuity points, and one which is not sensitive but has no equicontinuity points. Finally, we show that (positively) expansive nuca are sensitive. 1 Introduction Non-uniform cellular automata ( nuca ) are an extension of cellular automata ( ca ), which are machines that operate on configurations - grids of cells coloured by an alphabet. In both, each cell simultaneously observes its neighbouring cells and changes its state depending on the state of the neighbourhood. A uniform ca transforms all cells with the same local rule, while while a nuca uses different local rules in different cells. The local rules of a nuca are given by a fixed local rule distribution. Cellular automata are a powerful tool in simulating systems based on local transformations, and nuca provide a generalization capable of simulating systems with variation in their local behaviour. The dynamical properties of uniform ca have been studied extensively, but many of them no-longer apply in the setting of nuca . For example, the well-known Garden of Eden theorem for uniform ca does not hold for nuca . However, some properties, such as the Garden of Eden theorem, can be recovered in nuca when the distribution of local rules is recurrent or uniformly recurrent [ 3 ] . The properties we examine are reversibility, balance, sensitivity and expansivity. There are implications known to hold for ca which don’t necessarily hold for nuca in general: all bijective ca are reversible, all surjective ca are balanced, a ca is either sensitive or has a dense set of equicontinuity points, and a (positively) expansive ca is sensitive. We find (positively) expansive nuca are still sensitive, but the other statements all have counter-examples. We also show that the reversibility of bijective nuca can be recovered when the rule distribution is uniformly recurrent, and the balance of surjective nuca when the distribution is recurrent. Additionally we show that bijective nuca are balanced. 2 Definitions Non-uniform cellular automata may be defined over any group, but in this work we only consider the 1-dimensional case of nuca over \mathbb{Z} . First, a few background definitions are needed. Definition 1 Let \Sigma be a finite set called a state set . A configuration (on \mathbb{Z} ) is an element c\in\Sigma^{\mathbb{Z}} . Definition 2 A cell is an element x\in\mathbb{Z} . A domain is any subset D\subseteq\mathbb{Z} . If D is finite, we call it a finite domain . Let \Sigma be a state set and c\in\Sigma^{\mathbb{Z}} a configuration. A pattern is any p\in\Sigma^{D} for some domain D . If D is finite, we call p a finite pattern . We use c_{|D}\in\Sigma^{D} to denote the pattern such that for any x\in D , c_{|D}(x)=c(x) . The space \Sigma^{\mathbb{Z}} equipped with Cantor’s topology and is known to be compact [ 1 ] . In contrast with uniform ca , which are defined by a local rule, a nuca is defined by a local rule distribution, which is a special configuration that determines which local rule is used in which cell. Definition 3 Let \Sigma be a state set. A radius r local rule is a function f:\Sigma^{2r+1}\rightarrow\Sigma . A finite set of local rules \mathcal{\mathcal{R}} is called a rule set . Note that defining local rules with radial neighbourhoods is equivalent to defining them with arbitrarily shaped neighbourhoods. Now we are ready to define nuca . Definition 4 A non-uniform cellular automaton (or nuca ) is a tuple A=(\Sigma,\mathcal{R},\theta) , where \Sigma is a state set, \mathcal{R} is a rule set, and \theta\in\mathcal{R}^{\mathbb{Z}} is a rule distribution. The global transition function of A is the function H_{\theta}:\Sigma^{\mathbb{Z}}\rightarrow\Sigma^{\mathbb{Z}} such that for c\in\Sigma^{\mathbb{Z}} , x\in\mathbb{Z} , \displaystyle H_{\theta}(c)(x)=\theta(x)(c(x-r),\ldots,c(x+r)), where r\in\mathbb{Z}_{+} is the radius of the local rule \theta(x) . If |\mathcal{R}|=1 then the nuca is a uniform cellular automaton (or ca ). We generally equate a nuca with its transition function. Let us define a few more concepts used throughout the work. The definitions of recurrence and uniform recurrence are equivalent with the usual topological definitions for subshifts. Definition 5 Let \theta\in\mathcal{R}^{\mathbb{Z}} be a rule distribution, and suppose \theta(x) is a radius r rule. We call the domain N_{\theta}(x)=[x-r,x+r] the neighbourhood of x . If D\subseteq\mathbb{Z} is a domain, we call the domain N_{\theta}(D)=\bigcup_{x\in D}N_{\theta}(x) the neighbourhood of D . Definition 6 Let \Sigma be a state set. The left-shift is the function \sigma:\Sigma^{\mathbb{Z}}\rightarrow\Sigma^{\mathbb{Z}} which maps c\in\Sigma^{\mathbb{Z}} such that \sigma(c)(x)=c(x+1) for all x\in\mathbb{Z} . Similarly, we call the function \sigma^{-1} the right shift . Note that \sigma\circ H_{\theta}=H_{\sigma(\theta)}\circ\sigma . If p\in\Sigma^{D} and q\in\Sigma^{C} are patterns and there is k\in\mathbb{Z} such that C=D+k and p(x)=q(x+k) for any x\in D , then we call q a translated copy (or simply copy ) of p . If D\cap(D+k)=\emptyset , the copies are disjoint . Definition 7 Let c\in\Sigma^{\mathbb{Z}} be a configuration. The configuration c is (spatially) recurrent if for any finite D\subseteq\mathbb{Z} there is C\subseteq\mathbb{Z} such that D\neq C and c_{|C} is a copy of c_{|D} . The configuration c is (spatially) uniformly recurrent if for any finite D\subseteq\mathbb{Z} there is n\in\mathbb{Z}_{+} such that for any x\in\mathbb{Z} , there is C\subseteq[x,x+n] such that c_{|C} is a copy of c_{|D} . The same concepts are defined for rules rule distributions \theta\in\mathcal{R}^{\mathbb{Z}} when \mathcal{R} is finite. 3 Reversibility Informally, we call a nuca H reversible if there exists an inverse nuca H^{-1} , such that H\circ H^{-1}=H^{-1}\circ H is the identity function. In uniform ca reversibility is equivalent with bijectivity, which in turn is equivalent with injectivity. Definition 8 Let \Sigma be a state set. By \mathrm{id}:\Sigma^{\mathbb{Z}}\rightarrow\Sigma^{\mathbb{Z}} we denote the identity function. Definition 9 Let \mathcal{R}_{1} be a rule set and \theta\in\mathcal{R}_{1}^{\mathbb{Z}} . If there exists finite rule set \mathcal{R}_{2} and \phi\in\mathcal{R}_{2}^{\mathbb{Z}} such that H_{\phi}=H_{\theta}^{-1} , then the automaton H_{\theta} is reversible . Obviously, a reversible nuca is bijective. For uniform ca , the converse requires a non-trivial proof based on the compactness of the configuration space \Sigma^{\mathbb{Z}} . If we allow nuca to have infinitely many rules, the converse is also simple. This follows from the fact that nuca (allowing infinitely many rules) are exactly the continuous functions over the Cantor set [ 2 ] , and the fact that the inverse of a bijective continuous function is also continuous. Then the inverse of a bijective nuca is a continuous function over the Cantor set, thus