ON THE EFFECTS OF NOISE AND SPEED ON COMPUTATIONS

In this paper we propose a model that captures the influence of noise and speed on the correct behavior of a computing device situated in a dynamic environment. Within this model we analyze the relation between structural properties of automata and their immunity to noise. We pro ve upper and lower bounds on the effect of noise for various classes o f finite automata. In addition, we show similar relationships between relative speeds of the automaton and the environment and the accuracy of computation. Our model, combining basic notions from algebraic auto mata theory and the theory of stochastic processes, can serve as a sta rting point for a rigorous theory of computational systems embedded in the real world.