Physical modelling is the process of finding a mathematical description that is consistent with observations of the physical world. Many models, from the heat equation to the Schroedinger equation, are formulated in the continuous language of differential equations. Space and time are thought of as a continuum, hence the models potentially specify detail down to arbitrarily fine scales. Discrete physical models are an attractive alternative to continuous models such as partial differential equations. In discrete models, space is treated as a lattice, and time is discrete. Physical processes are modelled by rules that typically depend on a small number of nearby locations. From a theoretical standpoint, such models have the advantage that they do not have infinitely many locations per unit volume. From a practical standpoint, they correspond to the discrete structure of digital computing machines, and this makes them natural for simulation.
Formulations in which space and time are discrete are widely used. Most often, this is done in order to approximate continuous models: space and time are partitioned in order to integrate a model in the form of a differential equation on a computer.
By contrast, some models have been proposed as alternatives to, rather than an approximations of, differential equations.[6] Cellular automata (CA's)[3] and lattice gases [5] are widely-used classes of discrete models in which space is modelled as a regular lattice, with a state associated with each lattice site. Periodically, all sites on the lattice simultaneously update their states. The rule that determines the new state is local, depending only on nearby sites, and is a function of the state of the neighboring sites in the previous time step. CA's and lattice gases have been used with success to study many different phenomena such as fluid dynamics, polymers, and molecular dynamics.
There are two main features that all commonly-used discrete models share. First, space is a regular lattice. Update rules typically exploit this - for example, by using the fact that two neighbors are at ``right angles'' to, or ``opposite,'' each other. Second, although the update rule is local in space, the updates for all sites are globally synchronized with each other. The rule is a function of the states from the previous time step, before any of the updates from the current time step have happened. These conditions are very convenient for simulation because they correspond to the structure of the machines used to simulate the models.
We might well ask, however, on the grounds of minimalism, whether global synchronization and crystalline geometry are inherent in any discrete formulation. Is it possible to do without these conditions and still have a useful physical model? Or are they somehow fundamental?
There are reasons to believe that a regular lattice is not fundamental. With this geometry, a particular set of directions are preferred over others, namely the axes of the lattice. Likewise, in most discrete models the update rule operates locally in space, but we might ask whether we can devise rules such that the update can happen independently of other sites in time as well, rather than happen as part of a single global update. Most discrete models depend critically on both the regularity of the lattice and on a universal clock.
These conditions need to be examined if we want to think of discrete models as physical models themselves rather than as approximations of other models. We thus investigates the question of how minimal a useful discrete model can be.
We will show that it is possible to formulate a useful discrete model that does not rely on synchrony or regular geometry. Section 2 makes more concrete what is meant by ``local'' in discrete models. We will introduce the constraints that capture what it means for updates to happen independently of each other in time. A key constraint is that each site has no information about where others are in relation to it (other than whether they are neighbors), or at what time they update. If a discrete model works with these constraints, it does not rely on synchronization or regular geometry.
Section 3 outlines a class of discrete models that satisfy these constraints. This Section then presents an example of a useful instance of this class of models, a model of wave phenomena. It is shown that all interaction can be reduced to transactions between pairs of sites.
Section 4 presents a method for simulating the asynchronous, parallel model on a sequential machine, and gives results of simulations of the discrete wave model. The model is shown to agree both qualitatively and quantitatively with partial differential equation models.
Finally, Section 5 compares physical models to models of computation. It is shown that the model we introduce corresponds to a different kind of highly parallel computing machine known as an amorphous computer.