Time-reversal symmetries in two-dimensional reversible partitioned cellular automata and their applications. Issue 5 (3rd September 2022)

• Record Type: Journal Article
• Authors: Morita, Kenichi
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 37:Issue 5(2022)
• Page Start: 479
• Page End: 511
• Publication Date: 2022-09-03
• Subjects: Time-reversal symmetry -- T-symmetry -- reversible cellular automaton -- partitioned cellular automaton -- backward evolution process -- inverse functional module; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2022.2102169
• Languages: English
• ISSNs: 1744-5760

Abstract

Abstract : Time-reversal symmetry (T-symmetry) in a reversible cellular automaton (CA) is the property in which forward and backward evolutions of configurations are governed by the same local transition function. We show that the framework of partitioned cellular automata (PCAs) is useful to study T-symmetries of reversible CAs. Here, we investigate reversible elementary square PCAs (ESPCAs) and reversible elementary triangular PCAs (ETPCAs), and prove that a large number of reversible ESPCAs and all reversible ETPCAs are T-symmetric under some kinds of simple transformations on configurations. As applications, these results are used to find and analyse backward evolution processes in reversible PCAs. For example, for a given functional module implemented in a reversible PCA, such as a reversible logic element, we can obtain its inverse functional module very easily using its T-symmetry.