Directional Movement of a Collective of Compassless Automata on a Square Lattice of Width 2
摘要
The author considers the problem of preserving the direction of movement by a collective of finite automata on a two-dimensional integer lattice of width two whose elements (vertices) are anonymous. The automata do not distinguish between equally labeled vertices by their direction coordinates (i.e., each automaton has no compass). The collectives consisting of a single automaton and several pebbles whose layout is completely determined by the automaton are considered. It is proved that a collective of an automaton and a maximum of three pebbles cannot maintain movement direction on the lattice, but a collective of an automaton and four pebbles can.