Transitive Cellular Automata Are Sensitive

Abstract

The notion of chaos is a very appealing one, and it has intrigued several scientists (see [1, 2, 5, 7] for some work on the properties that characterize a chaotic process). There are simple deterministic dynamical systems that exhibit unpredictable behavior. Though counter-intuitive, this fact has a very clear eEplanation. The lack of infinite precision causes a loss of information which is dramatic for some processes which quickly lose their deterministic nature to assume a non deterministic (unpredictable) one. This observation leads to the intuition that investigations about chaos are intrinsically of an interdisciplinary nature. Indeed, the study of chaos draws its deeper methods of analysis from mathematics, it owes to physics a treasure of important problems, and it brings challenges to the science of computing. The reason for this last fact relies on the above observation that a chaotic behavior lies in between two different modes of computation, determinism and nondeterminism, whose quantitative comparison is central to the main open questions in the theory of computing [6]. A chaotic phenomenon can indeed be viewed as a deterministic one, in the presence of infinite precision, and as a nondeterministic one, in the presence of finite precision constraints (see Figure 1). Thus one should look at chaotic processes as at processes merged into time, space, and precision bounds, which are the key resources in the science of computing.