Decision Algorithms for Reversibility of One-dimensional Non-linear Cellular Automata Under Null Boundary Conditions

The property of reversibility is quite meaningful for the classic theoretical computer science model,cellular automata.For the reversibility problem for a CA under null boundary conditions,while linear rules have been extensively studied,the non-linear rules have so far been rarely explored.The paper investigates the reversibility problem of general one-dimensional CA on a finite field $\mathbb{Z}_{p}$,and proposes an approach to optimize the Amoroso's infinite CA surjectivity detection algorithm.Based on this,this paper proposes an algorithm for determining the invertibility of one-dimensional CA under zero boundary conditions,including an algorithm for determining the strict invertibility of one-dimensional CA under zero boundary conditions,and an algorithm for calculating the invertibility function of one-dimensional CA under zero boundary conditions based on barrel chain.These decision algorithms work for not only linear rules but also non-linear rules.In addition,it has been confirmed that the reversibility function always has a period,and its periodicity is related to the periodicity of the corresponding bucket chain.Some of the experiment results of reversible CA are presented in this paper,complementing and validating the theoretical aspects,and thereby further supporting the research conclusions of this paper.