Sequentializing cellular automata
- PDF / 611,323 Bytes
- 14 Pages / 595.276 x 790.866 pts Page_size
- 9 Downloads / 251 Views
(0123456789().,-volV)(0123456789(). ,- volV)
Sequentializing cellular automata Jarkko Kari1 • Ville Salo1
•
Thomas Worsch2
Ó The Author(s) 2019
Abstract We study the problem of sequentializing a cellular automaton without introducing any intermediate states, and only performing reversible permutations on the tape. We give a decidable characterization of cellular automata which can be written as a single sweep of a bijective rule from left to right over an infinite tape. Such cellular automata are necessarily left-closing, and they move at least as much information to the left as they move information to the right. Keywords Cellular automata Closing Sequentialization
1 Introduction Cellular automata are models of parallel computation, so when implementing cellular automata on a sequential architecture, one cannot simply update the cells one by one—some cells would see already updated states and the resulting configuration would be incorrect. The simplestto-implement solution is to hold two copies of the current configuration in memory, and map ðx; xÞ7!ðx; GðxÞÞ7! ðGðxÞ; GðxÞÞ. This is wasteful in terms of memory, and one can, with a bit of thinking, reduce the memory usage to a constant by simply remembering a ‘wave’ containing the previous values of the r cells to the left of the current cell, where r is the radius of the CA. Here, we study the situation where the additional memory usage can be, in a sense, dropped to zero—more precisely we remember only the current configuration x, and to apply the cellular automaton we sweep a permutation v : Sn ! Sn from left to right over x (applying it consecutively to all length-n subwords of x). The positions where the sweep starts may get incorrect values, but after a bounded number of steps, the rule should start writing the image of the cellular automaton. We formalize this in two
Research supported by the Academy of Finland Grants 296018 and 2608073211. & Ville Salo [email protected] 1
University of Turku, Turku, Finland
2
Karlsruhe Institute of Technology, Karlsruhe, Germany
ways, with ‘sliders’ and ‘sweepers’, which are two ways of formally dealing with the problem that sweeps ‘start from infinity’. It turns out that the cellular automata that admit a sliding rule are precisely the ones that are left-closing (Definition 5), and whose number of right stairs (see Definition 6) of length 3m divides jSj3m for large enough m. This can be interpreted as saying that the the average movement ‘with respect to any prime number’ is not to the right. See Theorems 2 and 3 for the precise statements, and Sect. 4 for decidability results. We introduce the sweeping hierarchy where left-to-right sweeps and right-to-left sweeps alternate, and the closing hierarchy where left-closing and right-closing CA alternate. We show that the two hierarchies coincide starting from the second level. We do not know if the hierarchies collapse on a finite level.
1.1 Preliminaries We denote the set of integers by Z. For integers i j we write [i, j) for fx 2 Z j i x\jg and [i, j] for ½i;
Data Loading...
