Universal computation and physical dynamics

Abstract

A dynamical system is said to be computationally universal if it can be programmed through its initial condition to perform and digital computation. Such systems include traditional abstract computers such as Turing machines and cellular automata, as well as more physical models such as hard sphere gases and even a single particle in an appropriately shaped box. Because of the ability of any two such systems to simulate one another, they are all equivalent in the range of computations they can perform; and the global dynamics of any one of them provides a microcosm of all cause/effect relations that can be expressed by deductive logic or numerical simulation. This allows universal computers to be used to define in an objective manner that sort of complexity which increases when a self-organizing system organizes itself. © 1995.