Embedding Computation in One-Dimensional Automata by Phase Coding Solitons

Abstract:

We show that some kind of meaningful computation can be embedded in very simple, microscopically homogeneous, one-dimensional automata - filter automata with a parity next-state rule. A systematic procedure is given for generating moving, periodic structures ("particles"). These particles exhibit soliton-like properties; that is, they often pass through one another with phase shifts. We then discuss ways to encode information in the phase of these particles. Finally, the search for useful logical operations is reduced to a search for paths in certain graphs. As a demonstration of principle, we give the details
of implementing a carry-ripple adder.