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

E. G. Kondakova ; A. Ya. Kanel-Belov

Čebyševskij sbornik, Tome 20 (2019) no. 3, pp. 296-315.

Résumé

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 $\mathbb{Z}^2$ and cannot bypass $\mathbb{Z}^3$; the c ++ robot bypasses $\mathbb{Z}^4$ and cannot bypass $\mathbb{Z}^5$; a robot with a stone and a flag bypasses $\mathbb{Z}^6$ and cannot bypass $\mathbb{Z}^7$; a robot with a stone and a flag plane bypasses $\mathbb{Z}^8$ and cannot bypass $\mathbb{Z}^9$.

Détail

Keywords: maze traversal, finite state machine.

Bibliographie

[1] Kilibarda G., Kudryavtsev V. B., Ushchumlich Sh. M., “Dependent systems of automatic machines in labyrinths”, Discrete Mathematics and Applications, 1987

[2] Kilibarda G., “About the difficulty of automatically navigating of labyrinths”, Discrete Mathematics and Applications, 1993

[3] Kilibarda G., Kudryavtsev V. B., Ushchumlich Sh. M., “Dependent systems of automatic machines in labyrinths”, Discrete Mathematics and Applications, 2003

[4] Anjans A, The behavior of deterministic and probabilistic automatic machines in labyrinths, PhD Thesis, Riga, 1987

[5] Kilibarda G., Kudryavtsev V. B., Ushchumlich Sh.M, “Collectives of automatic machines in labyrinths”, Discrete Mathematics and Applications, 2003

[6] Kilibarda G., Kudryavtsev V.B, Ushchumlich Sh.M, “About labyrinths-trap for collectives of automatic machines”, Discrete Mathematics and Applications, 1993

[7] Kilibarda G., Kudryavtsev V.B, Ushchumlich Sh.M, “Systems of automatic machines in labyrinths”, Discrete Mathematics and Applications, 2006

[8] Spitzer F., Principles of Random Walks, Van Nostrand, 1964 | MR

[9] Shiryaev A, Probability, MCCNMO, M., 2004

[10] Dynkin E. B., Yushkevich A. A., Theorems and problems about processes of Markov, Nauka, M., 1967 | MR