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

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





Для просмотра файлов Вам могут потребоваться








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


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

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

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

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

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