ИСТИНА

Пусть $G$~-- конечно порожденная группа, $a_1,\dots,a_s$~-- ее образующие, $\Gamma$~-- граф Келли группы $G$ относительно набора $a_1,\dots,a_s$. Система автоматов {\it обходит граф $\Gamma$}, если для любой вершины $v\in \Gamma$ найдется момент времени когда один из автоматов ее посетит. \medskip {\bf Теорема 1. } {\it Если $G$ содержит элемент бесконечного порядка, то существует алгоритм обхода графа $\Gamma$ четырьмя конечными автоматами. } \medskip {\bf Теорема 2. } {\it Если $G$ не содержит элемент бесконечного порядка, то для любого конечного семейства взаимодействующих произвольным образом конечных автоматов существует конечная область в графе $\Gamma$, которую они не покинут. }