Completeness problem of one-dimensional binary scope-3 tessellation automata

摘要

In this report we deal with the question of whether or not, for a given tessellation automaton, there exists a finite state pattern of the array that can never be assumed by the array no matter what sequence of global transformations is applied to a certain canonical starting pattern. We are exclusively concerned with the one-dimensional tessellation automata. We show that any finite state pattern can evolve from the starting pattern in the case where the neighborhood scope is three or more and the cell in the array has 2i3j states (i, j=0,1,2,…).