Об обходе пространства Роботом снабженным датчиком случайных чисел

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