Reference : Shift-symmetric configurations in two-dimensional cellular automata: Irreversibility,... |

Scientific journals : Article | |||

Physical, chemical, mathematical & earth Sciences : Physics | |||

Computational Sciences; Physics and Materials Science | |||

http://hdl.handle.net/10993/39768 | |||

Shift-symmetric configurations in two-dimensional cellular automata: Irreversibility, insolvability, and enumeration | |

English | |

Banda, Peter [University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB) > >] | |

Caughman, John [Portland State University > Department of Mathematics and Statistics] | |

Cenek, Martin [University of Portland > Shiley School of Engineering] | |

Teuscher, Christof [Portland State University > Department of Electrical and Computer Engineering] | |

25-Jun-2019 | |

Chaos | |

AIP Publishing | |

American Institute of Physics | |

29 | |

6 | |

063120 | |

Yes (verified by ORBi^{lu}) | |

International | |

1054-1500 | |

1089-7682 | |

[en] configuration shift-symmetry ; toroidal translation invariance ; two-dimensional cellular automata ; group theory ; pattern formation ; irreversibility ; insolvability ; enumeration ; symmetry detection ; prime factorization ; prime orbit ; mutually-independent generators ; leader election ; spontaneous symmetrization hypothesis | |

[en] The search for symmetry as an unusual yet profoundly appealing phenomenon, and the origin of regular, repeating configuration patterns have long been a central focus of complexity science and physics. To better grasp and understand symmetry of configurations in decentralized toroidal architectures, we employ group-theoretic methods, which allow us to identify and enumerate these inputs, and argue about irreversible system behaviors with undesired effects on many computational problems. The concept of so-called configuration shift-symmetry is applied to two-dimensional cellular automata as an ideal model of computation. Regardless of the transition function, the results show the universal insolvability of crucial distributed tasks, such as leader election, pattern recognition, hashing, and encryption. By using compact enumeration formulas and bounding the number of shift-symmetric configurations for a given lattice size, we efficiently calculate the probability of a configuration being shift-symmetric for a uniform or density-uniform distribution. Further, we devise an algorithm detecting the presence of shift-symmetry in a configuration.
Given the resource constraints, the enumeration and probability formulas can directly help to lower the minimal expected error and provide recommendations for systemâ€™s size and initialization. Besides cellular automata, the shift-symmetry analysis can be used to study the non-linear behavior in various synchronous rule-based systems that include inference engines, Boolean networks, neural networks, and systolic arrays. | |

Researchers | |

http://hdl.handle.net/10993/39768 | |

10.1063/1.5089889 | |

https://aip.scitation.org/doi/10.1063/1.5089889 |

File(s) associated to this reference | ||||||||||||||

| ||||||||||||||

All documents in ORBi^{lu} are protected by a user license.