Get 20M+ Full-Text Papers For Less Than $1.50/day. Subscribe now for You or Your Team.

Learn More →

Two-state, reversible, universal cellular automata in three dimensions

Two-state, reversible, universal cellular automata in three dimensions Two-state, Reversible, Universal Cellular Automata in Three Dimensions Daniel B. Miller Carnegie Mellon University Nasa Research Park Moffett Field, CA 94035 650-335-2806 Edward Fredkin Carnegie Mellon University Nasa Research Park Moffett Field, CA 94035 650-603-7038 four distinct states. The simplest 2-D reversible cellular automata we are aware of that is known to be capable of universal computation is introduced by Margolus in [9], and is based on the so-called BBM (Billiard Ball Model) as presented in [4]. The Margolus CA is a two-state, reversible CA in two dimensions; to our knowledge it has not been ascertained whether this CA is also a universal constructor1. In this paper we will describe the general class of CA's we refer to as 'Salt' automata. We then proceed to analyze one specific rule set within this new class. We will show that the CA in question is a reversible automata, and is capable of universal computation, through the existence of 'gliders' that interact to perform logic operations. We will offer strong evidence that this particular CA is also capable of so-called universal construction, through the interaction of gliders strategically emitted from a central location. ABSTRACT A novel two-state, Reversible Cellular Automata (RCA) http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

Two-state, reversible, universal cellular automata in three dimensions

Association for Computing Machinery — May 4, 2005

Loading next page...
/lp/association-for-computing-machinery/two-state-reversible-universal-cellular-automata-in-three-dimensions-M8luOKgqIL

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

Datasource
Association for Computing Machinery
Copyright
Copyright © 2005 by ACM Inc.
ISBN
1-59593-019-1
doi
10.1145/1062261.1062271
Publisher site
See Article on Publisher Site

Abstract

Two-state, Reversible, Universal Cellular Automata in Three Dimensions Daniel B. Miller Carnegie Mellon University Nasa Research Park Moffett Field, CA 94035 650-335-2806 Edward Fredkin Carnegie Mellon University Nasa Research Park Moffett Field, CA 94035 650-603-7038 four distinct states. The simplest 2-D reversible cellular automata we are aware of that is known to be capable of universal computation is introduced by Margolus in [9], and is based on the so-called BBM (Billiard Ball Model) as presented in [4]. The Margolus CA is a two-state, reversible CA in two dimensions; to our knowledge it has not been ascertained whether this CA is also a universal constructor1. In this paper we will describe the general class of CA's we refer to as 'Salt' automata. We then proceed to analyze one specific rule set within this new class. We will show that the CA in question is a reversible automata, and is capable of universal computation, through the existence of 'gliders' that interact to perform logic operations. We will offer strong evidence that this particular CA is also capable of so-called universal construction, through the interaction of gliders strategically emitted from a central location. ABSTRACT A novel two-state, Reversible Cellular Automata (RCA)

There are no references for this article.