Faster Methods for Identifying Nontrivial Energy Conservation Functions for Cellular Automata

Abstract : The biggest obstacle to the efficient discovery of conserved energy functions for cellular auotmata is the elimination of the trivial functions from the solution space. Once this is accomplished, the identification of nontrivial conserved functions can be accomplished computationally through appropriate linear algebra. As a means to this end, we introduce a general theory of trivial conserved functions. We consider the existence of nontrivial additive conserved energy functions ("nontrivials") for cellular automata in any number of dimensions, with any size of neighborhood, and with any number of cell states. We give the first known basis set for all trivial conserved functions in the general case, and use this to derive a number of optimizations for reducing time and memory for the discovery of nontrivials. We report that the Game of Life has no nontrivials with energy windows of size 13 or smaller. Other $2D$ automata, however, do have nontrivials. We give the complete list of those functions for binary outer-totalistic automata with energy windows of size 9 or smaller, and discuss patterns we have observed.
Type de document :
Communication dans un congrès
Fatès, Nazim and Kari, Jarkko and Worsch, Thomas. Automata 2010 - 16th Intl. Workshop on CA and DCS, 2010, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS, pp.1-18, 2010, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01185499
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 14:16:58
Dernière modification le : mardi 7 mars 2017 - 15:06:49
Document(s) archivé(s) le : mercredi 26 avril 2017 - 10:08:16

Fichier

dmAL0101.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01185499, version 1

Collections

Citation

Leemon Baird, Barry Fagin. Faster Methods for Identifying Nontrivial Energy Conservation Functions for Cellular Automata. Fatès, Nazim and Kari, Jarkko and Worsch, Thomas. Automata 2010 - 16th Intl. Workshop on CA and DCS, 2010, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS, pp.1-18, 2010, DMTCS Proceedings. 〈hal-01185499〉

Partager

Métriques

Consultations de la notice

92

Téléchargements de fichiers

82