View article

We initiate a study of learning and testing dynamic environments, focusing on environments that evolve according to a fixed local rule. The (proper) learning task consists of obtaining the initial configuration of the environment, whereas for nonproper learning it suffices to predict its future values. The testing task consists of checking whether the environment has indeed evolved from some initial configuration according to the known evolution rule. We focus on the temporal aspect of these computational problems, which is reflected in two requirements: (1) it is not possible to “go back to the past” and make a query concerning the environment at time t after having made a query concerning time t′ > t, and (2) only a small portion of the environment is inspected in each time unit.

We present several general results, extensive studies of two special cases, and a host of open problems. The general results illustrate the …