ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

14. Mathematical Aspects of Computer Science

1991 MS Classification: 68Q05, 68Q80, 94C10, 92B05 Adamatzky Andrew, University of the West of England, Bristol, UK On computation universality of excitable lattices We describe two and three dimensional cellular-automata models of excitable lattices that are capable to universal computation in the sense of realization of interaction logical gates. On the exploring all possible binary collisions between movable localized excitations we compile the catalogue of the logical gates that are constructed in the excitable lattices. The complexity of the logical gates and the possible realizations of the registers and counters are discussed. The place of the excitable lattices in the hierarchy of computation universal models and their high affinity to the real life analogues confirm that excitable lattices are the minimal models of real-life dynamical universal computers.