Probabilistic methods of bypass of the labyrinth using stones and random number generator

Abstract

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 [4] flags. Such problems help to develop the mathematical apparatus in this area, in addition, in this work we investigate the almost unexplored behavior of a robot with a random number generator. It is extremely important to transfer combinatorial methods developed by A. M. Raigorodsky in the problems of this topic.

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 Z² and cannot bypass Z³; the c ++ robot bypasses Z⁴ and cannot bypass Z⁵; a robot with a stone and a flag bypasses Z⁶ and cannot bypass Z⁷; a robot with a stone and a flag plane bypasses Z⁸ and cannot bypass Z⁹.