Существует широкий спектр задач посвященных возможности обхода лабиринта конечными автоматами. Они могут отличаться как типом лабиринта(это может быть любой граф, даже бесконечный), так и самими автоматами или их количеством. В частности у конечного автомата может быть память(магазин) или генератор случайных битов. В дальнейшем будем считать, что робот — это конечный автомат с генератором случайных битов, если не сказано иное. Кроме того в этой системе могут быть камни-объект, который конечный автомат может переносить по графу, и флажки- объект, наличие которого конечный автомат может только "наблюдать". Эта тема представляет интерес в связи с тем, что некоторые из этих задач тесно связаны с задачами из теории вероятности и сложности вычислений.
В данной работе продолжают решаться некоторые открытые вопросы, поставленные в диссертации Аджанса: обход роботом с генератором случайных битов целочисленных пространств при наличии камня и подпространства флажков [
Данная работа посвящена обходу лабиринта конечным автоматом с генератором случайных битов. Эта задача является частью активно развивающейся темы обхода лабиринта различными конечными автоматами или их коллективами, которая тесно связана с задачами из теории сложности вычислений и теории вероятности. В данной работе показано, при каких размерностях робот с генератором случайных битов и камнем может обойти целочисленное пространство с подпостранством флажков. В данной работе будет изучено поведение конечного автомата с генератором случайных битов на целочисленных пространствах. В частности доказано, что робот обходит Z2 и не может обойти Z3; робот c камнем обходит Z4 и не может обойти Z5; робот c камнем и флажком обходит Z6 и не может обойти Z7; робот c камнем и плоскостью флажков обходит Z8 и не может обойти Z9.
There is a wide range of problems devoted to the possibility of traversing the maze by finite automatons. They can differ as the type of maze (it can be any graph, even infinite), and the automata themselves or their number. In particular, a finite state machine can have a memory (store) or a random bit generator. In the future, we will assume that the robot — is a finite automaton with a random bit generator, unless otherwise stated. In addition, in this system, there can be stones-an object that the finite state machine can carry over the graph, and flags-an object whose presence the finite state machine can only "observe". This topic is of interest due to the fact that some of these problems are closely related to problems from probability theory and computational complexity.
This paper continues to address some of the open questions posed in Ajans’s thesis: traversal by a robot with a random bit generator of integer spaces in the presence of a stone and a subspace of [
This work is devoted to the maze traversal by a finite automaton with a random bit generator. This problem is part of the actively developing theme of traversing the maze by various finite automata or their teams, which is closely related to problems from the theory of complexity of calculations and probability theory. In this work it is shown what dimensions a robot with a generator of random bits, and you can get around stone integer space with flag subspace. In this paper, we will study the behavior of a finite automaton with a random bit generator on integer spaces. In particular, it is proved that the robot bypasses Z2 and cannot bypass Z3; the c ++ robot bypasses Z4 and cannot bypass Z5; a robot with a stone and a flag bypasses Z6 and cannot bypass Z7; a robot with a stone and a flag plane bypasses Z8 and cannot bypass Z9.
The authors declare that there are no conflicts of interest present.