Solving the parity problem in one-dimensional cellular automata

DOI10.1007/S11047-013-9374-9MaRDI QIDQ272769zbMATH OpenOpenAlexFDO

Authors Heather Betel, Pedro P. B. de Oliveira, P. Flocchini

Publication date 21 April 2016

Published in Natural Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1208.2758

zbMATH Keywords

de Bruijn graphsdensity classificationelementary cellular automataemergent computationparity problem

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Abstract: We consider the parity problem in one-dimensional, binary, circular cellular automata: if the initial configuration contains an odd number of 1s, the lattice should converge to all 1s; otherwise, it should converge to all 0s. It is easy to see that the problem is ill-defined for even-sized lattices (which, by definition, would never be able to converge to 1). We then consider only odd lattices. We are interested in determining the minimal neighbourhood that allows the problem to be solvable for any initial configuration. On the one hand, we show that radius 2 is not sufficient, proving that there exists no radius 2 rule that can possibly solve the parity problem from arbitrary initial configurations. On the other hand, we design a radius 4 rule that converges correctly for any initial configuration and we formally prove its correctness. Whether or not there exists a radius 3 rule that solves the parity problem remains an open problem.

Recommendations

• scientific article; zbMATH DE number 7339755
• Problem solving on one-bit-communication cellular automata
• A perfect solution to the parity problem with elementary cellular automaton 150 under asynchronous update
• Improvement of a result on sequencing elementary cellular automata rules for solving the parity problem
• The Nilpotency Problem of One-Dimensional Cellular Automata
• scientific article; zbMATH DE number 2113947
• Exact solvability and quasiperiodicity of one-dimensional cellular automata
• Solving parity games using an automata-based algorithm
• On the conjugacy problem of cellular automata
• Computations on one-dimensional cellular automata

Cites work

• scientific article; zbMATH DE number 2042127 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 919587 (Why is no real title available?)
• scientific article; zbMATH DE number 2188483 (Why is no real title available?)
• Additive Cellular Automata
• Conservation of some dynamical properties for operations on cellular automata
• Distributed Computing: A Locality-Sensitive Approach
• Improvement of a result on sequencing elementary cellular automata rules for solving the parity problem
• On the directional dynamics of additive cellular automata
• On the relationship between fuzzy and Boolean cellular automata
• Solution of some conjectures about topological properties of linear cellular automata
• Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision
• The computational power of population protocols
• Very effective evolutionary techniques for searching cellular automata rule spaces

Cited in

(16)

• Mining a class of decision problems for one-dimensional cellular automata
• A fully operational framework for handling cellular automata templates
• Remarks on the cellular automaton global synchronisation problem: deterministic versus stochastic models
• scientific article; zbMATH DE number 7339755 (Why is no real title available?)
• Inversion of Mutually Orthogonal Cellular Automata
• A perfect solution to the parity problem with elementary cellular automaton 150 under asynchronous update
• Asynchronous cellular systems that solve the parity problem
• No six-cell neighborhood cellular automaton solves the parity problem
• Solving the parity problem with rule 60 in array size of the power of two
• A portfolio of classification problems by one-dimensional cellular automata, over cyclic binary configurations and parallel update
• Improvement of a result on sequencing elementary cellular automata rules for solving the parity problem
• A survey of cellular automata: types, dynamics, non-uniformity and applications
• Generalisation of a synchronous solution of the parity problem on cyclic configurations over a non-circulant graph
• Shift-equivalence of \(k\)-ary, one-dimensional cellular automata rules
• Synchronous solution of the parity problem on cyclic configurations, with elementary cellular automaton rule 150, over a family of directed, non-circulant, regular graphs
• Characterisation of the elementary cellular automata with neighbourhood priority based deterministic updates

This page was built for publication: Solving the parity problem in one-dimensional cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q272769)