Quarterly (winter, spring, summer, fall)
128 pp. per issue
7 x 10, illustrated
2014 Impact factor:

Artificial Life

Fall 2006, Vol. 12, No. 4, Pages 487-512
(doi: 10.1162/artl.2006.12.4.487)
© 2006 Massachusetts Institute of Technology
From Machine and Tape to Structure and Function: Formulation of a Reflexively Computing System
Article PDF (743.98 KB)

The relationship between structure and function is explored via a system of labeled directed graph structures upon which a single elementary read/write rule is applied locally. Boundaries between static (information-carrying) and active (information-processing) objects, imposed by mandate of the rules or physics in earlier models, emerge instead as a result of a structure-function dynamic that is reflexive: objects may operate directly on their own structure. A representation of an arbitrary Turing machine is reproduced in terms of structural constraints by means of a simple mapping from tape squares and machine states to a uniform medium of nodes and links, establishing computation universality. Exploiting flexibility of the formulation, examples of other unconventional “self-computing” structures are demonstrated. A straightforward representation of a kinematic machine system based on the model devised by Laing is also reproduced in detail. Implications of the findings are discussed in terms of their relation to other formal models of computation and construction. It is argued that reflexivity of the structure-function relationship is a critical informational dynamic in biochemical systems, overlooked in previous models but well captured by the proposed formulation.