This paper is written from the perspective of a computer scientist and addressed to theoretical physicists. As a consequence it may seem somewhat unusual, but rest assured, everything is really quite simple! The point of this paper is that the study of certain phenomena from computer science suggests that there are computer systems (cellular automata) that may be appropriate as models for microscopic physical phenomena. Cellular automata are now being used to model varied physical phenomena normally modelled by wave equations, (...) fluid dynamics, Ising models, etc. We hypothesize that there will be found a single cellular automaton rule that models all of microscopic physics; and models it exactly. We call this field DM, for digital mechanics. (shrink)

This chapter explores some fundamental consequences of the correspondence between physical process and computations. Most physical questions may be answerable only through irreducible amounts of computation. Those that concern idealized limits of infinite time, volume, or numerical precision can require arbitrarily long computations, and so be considered formally undecidable. The behavior of a physical system may always be calculated by simulating explicitly each step in its evolution. Much of theoretical physics has, however, been concerned with devising shorter methods of calculation (...) that reproduce the outcome without tracing each step. Computational irreducibility is common among the systems investigated in mathematics and computation theory, but it may well be the exception rather than the rule, since most physical questions may be answerable only through irreducible amounts of computation. (shrink)