If billiard balls aren't creepy enough for you, live soldier crabs of the species Mictyris guinotae can be used in place of the billiard balls.
Robust Soldier Crab Ball Gate
Department of Earth and Planetary Sciences,
Kobe 657-8501, Japan.
Unconventional Computing Centre.
University of the West of England,
Bristol, United Kingdom.
Soldier crabs Mictyris guinotae exhibit pronounced swarming behavior. Swarms of the crabs are tolerant of perturbations. In computer models and laboratory experiments we demonstrate that swarms of soldier crabs can implement logical gates when placed in a geometrically constrained environment.
Following this explanation from the link:
"Theoretically, room‑temperature computer memory operating at the Landauer limit could be changed at a rate of one billion bits per second with energy being converted to heat in the memory media at the rate of only 2.85 trillionths of a watt (that is, at a rate of only 2.85 pJ/s). Modern computers use millions of times as much energy."
I understand that to flip a 1 to a 0 it is necessary to dissipate that energy into heat.
Edit: But also I'm not sure how reversibility avoids that.
INVERTIBLE CELLULAR AUTOMATA: A REVIEW.
Tommaso Toffoli and Norman Margolus.
MIT Laboratory for Computer Science.
Because of this "information-losslessness"
(ach!), ICA automatically obey the second principle
of thermodynamics and, more generally, display
a full-featured statistical mechanics analogous
to that of Hamiltonian systems. As additional
structure is introduced (for instance, particle
conservation), macroscopic mechanical features
such as elasticity, inertia, etc. naturally
emerge out of statistics itself. In sum, once we
make sure that it is conserved, information has an
irresistible tendency to take on a strikingly tangible
aspect (cf. ) to materialize itself.
When -- and how -- can a cellular automaton be rewritten as a lattice gas?
Tommaso Toffolia, Silvio Capobiancob, Patrizia Mentrastic.
Reversible computing and cellular automata - A survey.
On Invertible Cellular Automata. Karel Culik II.
One of the tripper far-reaching (to the end of the universe) applications of reversible computation is Tipler's "Omega Point," which he wrote about in "The Physics of Immortality".
Then again, maybe it's something like the 1996 LucasArts game Afterlife, where you simulate every different religion's version of heaven and hell at once.
The primary goal of the game is to provide divine and infernal services for the inhabitants of the afterlife. This afterlife caters to one particular planet, known simply as the Planet. The creatures living on the Planet are called EMBOs, or Ethically Mature Biological Organisms. When an EMBO dies, its soul travels to the afterlife where it attempts to find an appropriate "fate structure". Fate structures are places where souls are rewarded or punished, as appropriate, for the virtues or sins that they practiced while they were alive.
BTW, bit-flipping is a reversible operation!
If irreversible computations have an effect on entropy in the environment, does transmitting a bit so it is not lost have an interesting effect too, even if it is done with a conventional computer and not a reversible one?
The amount of data transmitted over the internet has reached over a zettabyte per year - does thermodynamics tell us anything interesting about the consequences? Yes, it produces heat, but beyond that...
We usually expel our waste bits as heat, so my understanding is that reversible computers could also be run without so much need for cooling.
Billiard Ball Cellular Automata conserve mass: particles are never created or destroyed, they just bounce off of each other and static "bumper" cells. Computing by "smoke and mirrors"! Or you could think of them as electrons, but BBCA don't have "wires" like other logical CA like JVN29, just empty space and gas and bumpers.
So you can't have a "not" gate, because it would have to make billiard balls out of nowhere if the input were zero (no billiard balls => many billiard balls). And you can't destroy billiard balls either, so there has to be somewhere for them to go after they're not needed any more. Like sending them flying out into the environment -- effectively generating heat!
When you change the direction of time, they come flying back in from deep space (or bouncing back through a chaotic atmosphere, depending on the temperature of the "environment"), and run the computation in reverse.
The Fredkin Gate and the Toffoli Gate are universal reversible logic gates: you can construct any logical expression with them, and they don't create or destroy billiard balls.
>The Fredkin gate is a circuit or device with three inputs and three outputs that transmits the first bit unchanged and swaps the last two bits if, and only if, the first bit is 1.
>[The Toffoli gate] is also known as the "controlled-controlled-not" gate, which describes its action. It has 3-bit inputs and outputs; if the first two bits are set, it inverts the third bit, otherwise all bits stay the same.
>Universality and Toffoli gate: Any reversible gate that consumes its inputs and allows all input computations must have no more input bits than output bits, by the pigeonhole principle. For one input bit, there are two possible reversible gates. One of them is NOT. The other is the identity gate, which maps its input to the output unchanged. For two input bits, the only non-trivial gate is the controlled NOT gate, which XORs the first bit to the second bit and leaves the first bit unchanged.
Here's a cool silent video by John Walker (Fourmilab, Autodesk) explaining Billiard Ball Cellular Automata in CelLab, and a link to the documentation!
>It is possible to perform all logical operations by collisions of perfect billiard balls with fixed objects and one another. A CelLab ( http://www.fourmilab.ch/cellab/ ) alternating lattice rule ( http://www.fourmilab.ch/cellab/manual/rules.html#Bbm ) models a billiard ball universe where collisions are perfect (albeit following different rules than balls on a table), and the system is reversible.
There are reversible and non-reversible variants of Billiard Ball Cellular Automata, and you can compose reversible CA to get other reversible CA. You can make reversible gas in "random" brownian motion, by changing the direction of the particles "randomly" based on a reversible pseudo-random number generating cellular automata run in parallel. For example, you could use "time tunnel" seeded with randomness as a pseudo random number generator:
But once you compose it with a non-reversible rule, you can't go back! To simulate "diffusion-limited aggregation" based on the brownian motion gas, you have to break reversibility by defining a "frozen" particle that freezes other particles that touch it. That breaks reversibility because there are several ways to get into the same frozen state, and it has no way to reconstruct which of those states preceded the frozen state, or how long it has been frozen. But it looks cool, like ice crystals nucleating around a speck of dust on a window pane!
>In your todo list, my favorites are the features that make the play more interactive, such as tools for constructing initial states, and anything that makes it easier for users to define their own CA rules. For interesting rules to play with, most of my favorites are in the paper Crystalline Computation , though I do have some additional favorites since that paper was written.
>The rules that Tom and I are most attached to are the ones that are closest to physics, and those are mostly reversible lattice gases (or their partitioning equivalents). I would also say that lattice gases provide the best model both for simulation efficiency using machines with RAM, and the simplest and most flexible mental model for constructing interesting local dynamics. This may be a bit of a distraction for you, but my best understanding of how to efficiently simulate lattice gases is discussed in the paper, An Embedded DRAM Architecture for Large-Scale Spatial-Lattice Computations . I believe the technique discussed there for embedding spatial lattices into blocks of DRAM is also the best for efficient simulation on PC's.
An Embedded DRAM Architecture for Large-Scale Spatial-Lattice Computations:
>My perspective is that CA's (and particularly lattice gases) are a modern and accessible version of classical field theories. Physicists have long used them as toy models to understand real physical phenomena, but their importance goes much deeper than that. It doesn't seem to be widely appreciated that most of the quantum revolution consisted of exposing the finite state nature of Nature! We looked closely at what we thought was a continuous world and we saw ... pixels! There is also some inscrutable screwiness that came along with that, but if you focus on just the finite-state part of the new physics, reversible lattice gases should be considered fundamental theoretical models. To quote from the end of my "Crystalline Computation" paper,
>"Although people have often studied CA’s as abstract mathematical systems completely divorced from nature, ultimately it is their connections to physics that make them so interesting. We can use them to try to understand our world better, to try to do computations better—or we can simply delight in the creation of our own toy universes. As we sit in front of our computer screens, watching to see what happens next, we never really know what new tricks our CA’s may come up with. It is really an exploration of new worlds—live television from other universes. Working with CA’s, anyone can experience the joy of building simple models and the thrill of discovering something new about the dynamics of information. We can all be theoretical physicists."
>As you can see, my personal inclination would be to emphasize the reversible stuff in the CAM-6 book, and the Crystalline Computation paper. And tell people they are being theoretical physicists!