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 Zp,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,inclu-ding 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 deci-sion 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 experi-ment results of reversible CA are presented in this paper,complementing and validating the theoretical aspects,and thereby fur-ther supporting the research conclusions of this paper.
NETL
NSTL
万方数据
