Об обходе лабиринтов автоматами, оставляющими нестираемые отметки

Проблема обхода плоских лабиринтов автоматами поставлена К. Шенноном в начале шестидесятых годов. Известно, что не существует конечного автомата, который обходил бы произвольный наперед заданный лабиринт. Поиски положительного решения проблемы обхода лабиринтов автоматами естественно вести в двух направлениях. Первое направление связано с рассмотрением более узких классов лабиринтов, а второе — с усилением возможностей автоматов при обходе ими лабиринтов. В данной работе показано, что существует автомат, оставляющий в вершинах лабиринта одну нестираемую отметку (краску) и обходящий произвольный прямоугольный лабиринт.