Note (g) for The Problem of Satisfying Constraints…Iterative improvement [of constraint satisfaction] The borders of the regions of black and white in the picture shown here essentially follow random walks and annihilate in pairs so that their number decreases with time like 1/ √ t .

One might have thought that in the literature of traditional science new models would be proposed all the time. … It does not help that models based on equations are often stated in a purely implicit form, so that rather than giving an actual procedure for determining how a system will behave—as a program does—they just give constraints on what the behavior must be, and provide no particular guidance about finding out what, if any, behavior will in fact satisfy these constraints.

Learning and memory, for example, can effectively occur in any system that has structures that form in response to input, and that can persist for a long time and affect the behavior of the system. … But at some level it can also be thought of as occurring whenever a constraint ends up getting satisfied—even say that a fluid flowing around a complex object minimizes the energy it dissipates. … There was a time when it was thought that practically any system that moves spontaneously and responds to stimuli must be

Existence and uniqueness [in PDEs] Unlike systems such as cellular automata, PDEs do not have a built-in notion of "evolution" or "time". Instead, as discussed on page 940 , a PDE is essentially just a constraint on the values of a function at different times or different positions. In solving a PDE, one is usually interested in determining values that satisfy this constraint inside a particular region, based on information about values on the edges.

.) • P (polynomial time): can be solved (with one processor) in a number of steps that increases like a polynomial in the input size. (Examples include evaluating standard mathematical functions and simulating the evolution of cellular automata and Turing machines.) • NP (non-deterministic polynomial time): solutions can be checked in polynomial time. (Examples include many problems based on constraints as well as simulating the evolution of multiway systems and finding initial conditions that lead to given behavior in a cellular automaton.) • PSPACE (polynomial space): can be solved with an amount of memory that increases like a polynomial in the input size.

There are some constraints on the details of the kinds of collisions that are possible, but reversible rules typically tend to work very much like ordinary ones. … But over the course of time the picture shows that the arrangement of particles becomes progressively more random.

Note (a) for Uniqueness and Branching in Time…Spacetime networks from multiway systems The main text considers models in which the steps of evolution in a multiway system yield a succession of events in time. An alternative kind of model, somewhat analogous to the ones based on constraints on page 483 , is to take the pattern of evolution of a multiway system to define directly a complete spacetime network.

When I started doing particle physics in the mid-1970s I assumed—like most theoretical scientists—that the results of experiments could somehow always be treated as rigid constraints on models. … And on the basis of this I spent great effort trying to see what might be wrong with the model—only to discover some time later that in fact the methodology of the experiment was flawed and its results were wrong.

Most ultimately attribute its validity to unknown constraints on initial conditions or measurements, though some appeal to external perturbations, to cosmology or to unknown features of quantum mechanics. … But only very special kinds of systems are in fact ergodic, and even in such systems, the time necessary to visit a significant fraction of all possible states is astronomically long.

Note (b) for The Problem of Satisfying Constraints…Combinatorial optimization The problem of coming as close as possible to satisfying constraints in an arrangement of black and white squares is a simple example of a combinatorial optimization problem. … In the main text we considered changing just one square at a time.