A Study on Reversible Rules of Probabilistic Cellular Automata

Abstract

Reversibility is an important phenomena in nature as well as in Computer Science. Obtaining plaintext back from ciphertext can be modeled as one kind of reversibility. Image restoration problem can be modeled as another kind of reversibility. Cellular automata (CA) are lattices and that are used as computation tools for modeling diverse complex dynamical systems. The CA evolve from one configuration to another over iterations using local transition rules. Number of cells that are allowed to undergo the local transition or update function in every time step varies from one kind of CA to another. In probabilistic CA (PCA), cells are selected randomly for update. Reversibility is one important issue in CA. Reversible CA are those CA which comes back to the initial state for any given inital state after some time steps. In this paper, we have studied the reversibility of a PCA where maximum two cells are selected randomly for possible updates in every time step. We have introduced a new tool, reachable state graph to understand the PCA reversibility dynamics and proposed a deterministic algorithm to find if a rule is reversible for PCA of arbitrary size.