Invertible behavior in elementary cellular automata with memory

详细信息	查看全文 | 推荐本文 |

• 作者：Juan C. Seck-Tuoh-Mora^a ; ^{jseck@uaeh.edu.mx} ; Genaro J. Martí ; nez^b ; ^c ; ^{genaro.juarez.martinez@googlemail.com} ; Ramon Alonso-Sanz^d ; ^{ramon.alonso@upm.es} ; Norberto Herná ; ndez-Romero^a ; ^{nhromero@uaeh.edu.mx}
• 关键词：Reversibility ; Memory ; Elementary cellular automata ; De Bruijn block
• 刊名：Information Sciences
• 出版年：2012
• 期刊代码：62_00200255
• 类别：cp
• 出版时间：15 September, 2012
• 卷：199
• 期：Complete
• 页码：125-132
• 文件大小：577 K

摘要

Elementary cellular automata (ECAs) have been studied for their ability to generate complex global behavior, despite their simplicity. One variation of ECAs is obtained by adding memory to each cell in a neighborhood. This process generates a provisional configuration in which the application of an evolution rule establishes the dynamics of the system. This version is known as an ECA with memory (ECAM). Most previous work on ECAMs analyzed the complex behavior taking chaotic ECAs. However, the present paper investigates reversible ECAMs as obtained from reversible and permutative ECAs. These ECAs have at least one ancestor for every configuration; thus, the correct permutation of states may specify the memory function to obtain reversible ECAMs. For permutative ECAs, which are often irreversible, we demonstrate that the use of a quiescent state and the correct manipulation of de Bruijn blocks produce reversible ECAMs.