RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары






Узлы и теория представлений
22 июня 2020 г. 18:30, г. Москва, онлайн Skype (@knots-in-moscow)
 


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

А. Я. Канель-Белов, Е. Г. Кондакова

Количество просмотров:
Эта страница:127

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

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021