188宝金博页面版

On the Computation Power of Finite Automatain Two-Dimensional EnvironmentsOleksiy Kurganskyy1,and Igor Potapov2,1Institute of Applied Mathematics and Mechanics,Ukrainian National Academy of Sciences, Donetsk, Ukrainekurgansk@gmx.de2Department of Computer Science,University of Liverpool, Liverpool, U.K.igor@csc.liv.ac.ukAbstract. In this paper we study the model of a nite state automa-ton interacting with innite two-dimensional geometric environments.We show that the reachability problem for a nite state automaton in-teracting with a quadrant of the plane extended by a power function, apolynomial function or a linear function is algorithmically undecidable,by simulating a Minsky machine. We also consider the environment de-ned by a parabola which impedes the direct simulation of multiplication.However we show that the model of a nite automaton interacting insidea parabola is also universal.1IntroductionFinite state automata arose as models of transducers of discrete information, i.e.models interacting with their environments [9]. Automata on picture languages[3,17], automata in labyrinths [2,10,11], communicating automata [14], multi-counter automata [15,7], a model of a computer in the form of interaction of acontrol automaton [4] are examples of such an interaction.The fundamental problem for systems where an automaton interacts with(possibly innite) environment is the reachability problem: “Does a global stateS (state of the automaton and state of the environment) belong to the set ofstates reachable from an initial global state”. The reachability problem hasconnections to many classical problems in automata theory such as diagnos-tic problems, distinguishability problems, searching in labyrinths, etc. One ofthe standard methods to show the undecidablity of the reachability problem forsome model is to prove that this computational model is universal.In this paper we consider the computational power of the reactive system,where an input/output automaton interacts with a two-dimensional geometricenvironment. In particular we consider the reactive system that includes a nitestate automaton (FSA) A and an innite environment E whereWork partially supported by RDF grant RDF/4417.Work partially supported by The Nueld Foundation grant NAL/00684/G.C.S. Calude, E. Calude and M.J. Dinneen (Eds.): DLT 2004, LNCS 3340, pp. 261–271, 2004.c Springer-Verlag Berlin Heidelberg 2004