Jump to ContentJump to Main Navigation
New Constructions in Cellular Automata$
Users without a subscription are not able to see the full content.

David Griffeath and Cristopher Moore

Print publication date: 2003

Print ISBN-13: 9780195137170

Published to Oxford Scholarship Online: November 2020

DOI: 10.1093/oso/9780195137170.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (oxford.universitypressscholarship.com). (c) Copyright Oxford University Press, 2021. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 04 August 2021

Simulating Digital Logic with the Reversible Aggregation Model of Crystal Growth

Simulating Digital Logic with the Reversible Aggregation Model of Crystal Growth

Chapter:
(p.211) Simulating Digital Logic with the Reversible Aggregation Model of Crystal Growth
Source:
New Constructions in Cellular Automata
Author(s):

George E. Homsy

Norman H. Margolus

Publisher:
Oxford University Press
DOI:10.1093/9780195137170.003.0012

We are concerned with understanding the implicit computation occurring in a physical model of crystal growth, the Reversible Aggregation (RA) model. The RA model is a lattice gas model of reversible cluster growth in a closed two-dimensional system, which captures basic properties of physics such as determinism, locality, energy conservation, and exact microscopic reversibility. There are three species of particles in the RA model: gas, heat, and crystal. A diffusing gas particle may aggregate when contacting the boundary of a crystal cluster. Latent heat is released during each aggregation event and is explicitly modeled by introducing a heat particle into a diffusing heat bath. Conversely a cluster member at the boundary of the crystal may absorb a heat particle and evaporate, becoming a diffusing gas particle. Allowing ourselves complete control over all the initial conditions of the model, we show that the RA model can simulate any logic circuit, and, hence, perform any computation. The mobile gas and heat particles are used as logic signals. The paths these particles take are the wires. Sequences of conditional crystallization events form the basis of the logic gates. We show how to embed a universal single use gate into the dynamics of the model, then show how to construct a reusable universal gate, showing the system is capable of space-efficient computation. We show how to build arbitrary logic circuits by interconnecting gates. This requires steering and routing the signals, delaying them, and letting them cross. Finally, we briefly discuss the relationship of computation in the RA model to computation in real physical systems. We examine the computational capabilities of a physical model of crystal growth, the Reversible Aggregation (RA) model [3], which captures basic properties of physics such as determinism, locality, energy conservation, and exact microscopic reversibility. The RA model is a lattice gas model of reversible cluster growth in a closed two-dimensional system. It was introduced as a microscopically reversible physical model for studying the thermodynamics of crystal growth and pattern formation. By microscopically reversible we mean that from any state in the system we can recover the previous state exactly.

Keywords:   Billiard Ball Model, Diffusion Limited Aggregation model, Fredkin gates, conservative logic gates, reusable logic gates, signal wires, switch gates, wires

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .