|
СЕМИНАРЫ |
|
Об обходе пространства Роботом снабженным датчиком случайных чисел А. Я. Канель-Белов, Е. Г. Кондакова |
|||
Аннотация: Доклад посвящен поведению Робота (конечного автомата) в лабиринте, снабженного датчиком случайных чисел и одним камешком. Цель Робота - обойти весь лабиринт. Это значит, что для любой его комнаты найдется момент времени (с вероятностью 1), когда Робот там побывает. Робот может оставлять камешек в комнате (вершине графа), проверять наличие камешка и уносить с собой. В качестве Лабиринта нас интересует целочисленная решетка. Без камешков, но с датчиком случайных чисел Робот может обойти двумерную решетку, но не может обойти решетку высшей размерности. С двумя камешками (и с датчиком случайных чисел) он может эмулировать машину Минского и тем самым обойти решетку произвольной размерности. В случае одного камешка он может обойти решетку размерности не выше 4, но не может обойти решетку высшей размерности. Удивительно, что если зафиксировать «кирпич», - который нельзя таскать, но можно распознавать клетку с ним, - то с помощью кирпича и камешка можно обойти решетку размерности 6, а если зафиксировать плоскость из кирпичей, то размерности 8. Для большей размерности фиксация подпространства кирпичей коразмерности 6, по всей видимости, не помогает. Однако, если при этом случайно расставить в клетках пространства числа 0 и 1 то осуществить обход уже можно. Доклад посвящен обсуждению возникающих вопросов. |