Nineteen elementary cellular automata rules (and their conjugation, reflection, reflected-conjugation) have been proven not maximum sensitive to synchronism, i.e. they do not have a different dynamics for each (non-equivalent) block-sequential update schedule (defined as ordered partitions of cell positions). In this work we present exact measurements of the sensitivity to synchronism for these rules, as functions of the size. These exhibit a surprising variety of values and associated proof methods, such as the isomer pairs of rule 128, and the connection to the bisection of Lucas numbers of rule 8.
Balbi, P., Formenti, E., Perrot, K., Riva, S., Ruivo, E. (2022). Non-maximal sensitivity to synchronism in elementary cellular automata: Exact asymptotic measures. THEORETICAL COMPUTER SCIENCE, 926, 21-50 [10.1016/j.tcs.2022.05.024].
Non-maximal sensitivity to synchronism in elementary cellular automata: Exact asymptotic measures
Riva S.
;
2022
Abstract
Nineteen elementary cellular automata rules (and their conjugation, reflection, reflected-conjugation) have been proven not maximum sensitive to synchronism, i.e. they do not have a different dynamics for each (non-equivalent) block-sequential update schedule (defined as ordered partitions of cell positions). In this work we present exact measurements of the sensitivity to synchronism for these rules, as functions of the size. These exhibit a surprising variety of values and associated proof methods, such as the isomer pairs of rule 128, and the connection to the bisection of Lucas numbers of rule 8.File | Dimensione | Formato | |
---|---|---|---|
Balbi-2022-TheorCompSci-VoR.pdf
Solo gestori archivio
Tipologia di allegato:
Publisher’s Version (Version of Record, VoR)
Licenza:
Tutti i diritti riservati
Dimensione
1.1 MB
Formato
Adobe PDF
|
1.1 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.