Attractors on finite sets: The dissipative dynamics of computing structures

Abstract

We present a theory of attractors on finite sets which is applicable to finite-state systems such as computing structures and other systems which display a hierarchy of organizations with a discrete time evolution. Because computing with attractive fixed points can lead to reliable behavior [B. A. Huberman and T. Hogg, Phys. Rev. Lett. 52, 1048 (1984)], the theory deals with dissipative processes, i.e., those which contract volumes in phase space. The stability of such systems is quantified and analytic expressions are obtained for the appropriate indices in some limiting cases. It is also shown that trees with ultrametric topologies provide the natural language for these systems. The theory is extended to include several practical constraints, and connections are made with experimental quantities which can be measured in particular architectures.