tailieunhanh - The reversibility problem for a family of two-dimensional cellular automata

In this paper the reversibility problem of a family of two-dimensional cellular automata is completely resolved. It is well known that the reversibility problem is a very difficult one in general. In order to determine whether a cellular automaton is reversible or not the reversibility of its rule matrix is studied via linear algebraic tools. | Turk J Math (2016) 40: 665 – 678 ¨ ITAK ˙ c TUB ⃝ Turkish Journal of Mathematics doi: Research Article The reversibility problem for a family of two-dimensional cellular automata 1 1,∗ ˙ 1 ¨ ˘ ˙ Mehmet Emin KORO GLU , Irfan S ¸ IAP , Hasan AKIN2 ˙ Department of Mathematics, Faculty of Arts and Sciences, Yıldız Technical University, Istanbul, Turkey 2 Department of Mathematics, Faculty of Education, Zirve University, Gaziantep, Turkey Received: • Accepted/Published Online: • Final Version: Abstract: In this paper the reversibility problem of a family of two-dimensional cellular automata is completely resolved. It is well known that the reversibility problem is a very difficult one in general. In order to determine whether a cellular automaton is reversible or not the reversibility of its rule matrix is studied via linear algebraic tools. However, in this particular study the authors consider a novel approach. By observing the algebraic structures of rule matrices that represent these families and associating them with polynomials in two variables in a quotient ring, the solution to the reversibility problem is simplified greatly. Hence, this approach not only drastically decreases the computational time for determining the reversibility of these families but also provides an explicit construction of reverse cellular automata in the case of the existence of their inverses. The paper concludes with a consideration of the rule matrices of these families in obtaining linear codes over group rings, which are referred to as zero-divisor codes. Key words: Cellular automata, reversibility, linear codes, group rings 1. Introduction Complex structures are generally divided into small pieces that are called cells and are studied accordingly. Observations have shown that the evolution of dynamical systems depends on the interactions among their neighboring cells. Due to this .