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

Существует широкий спектр задач посвященных возможности обхода лабиринта конечными автоматами. Они могут отличаться как типом лабиринта (это может быть любой граф, даже бесконечный), так и самими автоматами или их количеством. В частности у конечного автомата может быть память (магазин) или генератор случайных битов. В дальнейшем будем считать, что робот — это конечный автомат с генератором случайных битов, если не сказано иное. Кроме того в этой системе могут быть камни-объект, который конечный автомат может переносить по графу, и флажки- объект, наличие которого конечный автомат может только "наблюдать". Эта тема представляет интерес в связи с тем, что некоторые из этих задач тесно связаны с задачами из теории вероятности и сложности вычислений.
В данной работе продолжают решаться некоторые открытые вопросы, поставленные в диссертации Аджанса: обход роботом с генератором случайных битов целочисленных пространств при наличии камня и подпространства флажков [4]. Подобные задачи помогают развить математический аппарат в данной области, кроме того в этой работе мы исследуем практически не изученное поведение робота с генератором случайных чисел. Представляется чрезвычайно важным перенос комбинаторных методов, разработанных А. М. Райгородским в задачах этой тематики.
Данная работа посвящена обходу лабиринта конечным автоматом с генератором случайных битов. Эта задача является частью активно развивающейся темы обхода лабиринта различными конечными автоматами или их коллективами, которая тесно связана с задачами из теории сложности вычислений и теории вероятности. В данной работе показано, при каких размерностях робот с генератором случайных битов и камнем может обойти целочисленное пространство с подпостранством флажков. В данной работе будет изучено поведение конечного автомата с генератором случайных битов на целочисленных пространствах. В частности доказано, что робот обходит $\mathbb{Z}^2$ и не может обойти $\mathbb{Z}^3$; робот c камнем обходит $\mathbb{Z}^4$ и не может обойти $\mathbb{Z}^5$; робот c камнем и флажком обходит $\mathbb{Z}^6$ и не может обойти $\mathbb{Z}^7$; робот c камнем и плоскостью флажков обходит $\mathbb{Z}^8$ и не может обойти $\mathbb{Z}^9$.