Вероятностные методы обхода лабиринта с использованием камней и датчика случайных чисел

Аннотация

Существует широкий спектр задач посвященных возможности обхода лабиринта конечными автоматами. Они могут отличаться как типом лабиринта(это может быть любой граф, даже бесконечный), так и самими автоматами или их количеством. В частности у конечного автомата может быть память(магазин) или генератор случайных битов. В дальнейшем будем считать, что робот — это конечный автомат с генератором случайных битов, если не сказано иное. Кроме того в этой системе могут быть камни-объект, который конечный автомат может переносить по графу, и флажки- объект, наличие которого конечный автомат может только "наблюдать". Эта тема представляет интерес в связи с тем, что некоторые из этих задач тесно связаны с задачами из теории вероятности и сложности вычислений.

В данной работе продолжают решаться некоторые открытые вопросы, поставленные в диссертации Аджанса: обход роботом с генератором случайных битов целочисленных пространств при наличии камня и подпространства флажков [4]. Подобные задачи помогают развить математический аппарат в данной области, кроме того в этой работе мы исследуем практически не изученное поведение робота с генератором случайных чисел. Представляется чрезвычайно важным перенос комбинаторных методов, разработанных А. М. Райгородским в задачах этой тематики.

Данная работа посвящена обходу лабиринта конечным автоматом с генератором случайных битов. Эта задача является частью активно развивающейся темы обхода лабиринта различными конечными автоматами или их коллективами, которая тесно связана с задачами из теории сложности вычислений и теории вероятности. В данной работе показано, при каких размерностях робот с генератором случайных битов и камнем может обойти целочисленное пространство с подпостранством флажков. В данной работе будет изучено поведение конечного автомата с генератором случайных битов на целочисленных пространствах. В частности доказано, что робот обходит Z² и не может обойти Z³; робот c камнем обходит Z⁴ и не может обойти Z⁵; робот c камнем и флажком обходит Z⁶ и не может обойти Z⁷; робот c камнем и плоскостью флажков обходит Z⁸ и не может обойти Z⁹.