Grant: Discovery Grants Program - Individual

In science and technology, we often deal with systems that change their state with time, known as dynamical systems. These are often very complex - weather could serve as a good example in this respect. One of the principal problems that the theory of dynamical systems attempts to solve is the so-called forward problem: knowing the state of the system at a given time, predict its state in the future. In many processes observed in nature and technological applications, causal relationships between events can be established. Our knowledge of these causal relationships is often incomplete: for example, we may say that event A has been caused by event B1 or event B2, but are not sure which one. Similarly, event B1 could be caused by evens C1 or C2, etc. If we represent all those events by vertices of a graph and causal relationships between them by edges, we obtain a graph that often has a shape of a large tree with large number of branches splitting into sub-branches, sub-sub-branches, and so on. If we know what the structure of this ""causality tree"" is and know how probable events at a given level are, we can compute probabilities of events at lower levels, which is equivalent to having some sort of predictive capability: we can compute probabilities of later events based on probabilities of earlier events. This is equivalent to solving the forward problem in a probabilistic sense. Unfortunately, the aforementioned trees are often immensely complicated, thus limiting the practicality of this approach. In spite of this, if we restrict our attention to some specific class of dynamical processes, these trees in some cases exhibit remarkable regularities. We propose to study one such class of dynamical systems, known as cellular automata (CA). We will systematically search for regularities in ""causality trees"" associated with CA in order to find solutions of the associated forward problem and attempt to find general methods of producing such solutions in other dynamical systems, including those for which ""causality trees"" are not really trees, but more complex graphs.