Billiard-ball computer

Last updated
Fredkin and Toffoli billiard ball model of an AND gate. When a single billiard ball arrives at the gate through input 0-in or 1-in, it passes through the device unobstructed and exits via 0-out or 1-out. However, if a 0-in billiard ball arrives simultaneously as a 1-in billiard ball, they collide with each other in the upper-left-hand corner of the device and redirect each other to collide again in the lower-right-hand corner of the device. One ball then exits via 1-out and the other ball exits via the lower AND-output. Thus, the presence of a ball being emitted from the AND-output is logically consistent with the output of an AND gate that takes the presence of a ball at 0-in and 1-in as inputs. Toffoli BilliardBall-en.svg
Fredkin and Toffoli billiard ball model of an AND gate. When a single billiard ball arrives at the gate through input 0-in or 1-in, it passes through the device unobstructed and exits via 0-out or 1-out. However, if a 0-in billiard ball arrives simultaneously as a 1-in billiard ball, they collide with each other in the upper-left-hand corner of the device and redirect each other to collide again in the lower-right-hand corner of the device. One ball then exits via 1-out and the other ball exits via the lower AND-output. Thus, the presence of a ball being emitted from the AND-output is logically consistent with the output of an AND gate that takes the presence of a ball at 0-in and 1-in as inputs.

A billiard-ball computer, a type of conservative logic circuit, is an idealized model of a reversible mechanical computer based on Newtonian dynamics, proposed in 1982 by Edward Fredkin and Tommaso Toffoli. [1] Instead of using electronic signals like a conventional computer, it relies on the motion of spherical billiard balls in a friction-free environment made of buffers against which the balls bounce perfectly. It was devised to investigate the relation between computation and reversible processes in physics.

Contents

Simulating circuits with billiard balls

This model can be used to simulate Boolean circuits in which the wires of the circuit correspond to paths on which one of the balls may travel, the signal on a wire is encoded by the presence or absence of a ball on that path, and the gates of the circuit are simulated by collisions of balls at points where their paths cross. In particular, it is possible to set up the paths of the balls and the buffers around them to form a reversible Toffoli gate, from which any other Boolean logic gate may be simulated. Therefore, suitably configured billiard-ball computers may be used to perform any computational task. [2]

Simulating billiard balls in other models of computation

It is possible to simulate billiard-ball computers on several types of reversible cellular automaton, including block cellular automata and second-order cellular automata. In these simulations, the balls are only allowed to move at a constant speed in an axis-parallel direction, assumptions that in any case were already present in the use of the billiard ball model to simulate logic circuits. Both the balls and the buffers are simulated by certain patterns of live cells, and the field across which the balls move is simulated by regions of dead cells, in these cellular automaton simulations. [3]

Logic gates based on billiard-ball computer designs have also been made to operate using live soldier crabs of the species Mictyris guinotae in place of the billiard balls. [4] [5] [6]

See also

Related Research Articles

<span class="mw-page-title-main">Cellular automaton</span> Discrete model studied in computer science

A cellular automaton is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessellation structures, and iterative arrays. Cellular automata have found application in various areas, including physics, theoretical biology and microstructure modeling.

<span class="mw-page-title-main">DNA computing</span> Computing using molecular biology hardware

DNA computing is an emerging branch of unconventional computing which uses DNA, biochemistry, and molecular biology hardware, instead of the traditional electronic computing. Research and development in this area concerns theory, experiments, and applications of DNA computing. Although the field originally started with the demonstration of a computing application by Len Adleman in 1994, it has now been expanded to several other avenues such as the development of storage technologies, nanoscale imaging modalities, synthetic controllers and reaction networks, etc.

In logic circuits, the Toffoli gate, invented by Tommaso Toffoli, is a universal reversible logic gate, which means that any classical reversible circuit can be constructed from Toffoli gates. It 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 both set to 1, it inverts the third bit, otherwise all bits stay the same.

<span class="mw-page-title-main">Edward Fredkin</span> American physicist and computer scientist (1934–2023)

Edward Fredkin was an American computer scientist, physicist and businessman who was an early pioneer of digital physics.

Reversible computing is any model of computation where the computational process, to some extent, is time-reversible. In a model of computation that uses deterministic transitions from one state of the abstract machine to another, a necessary condition for reversibility is that the relation of the mapping from states to their successors must be one-to-one. Reversible computing is a form of unconventional computing.

Tommaso Toffoli is an Italian-American professor of electrical and computer engineering at Boston University where he joined the faculty in 1995. He has worked on cellular automata and the theory of artificial life, and is known for the invention of the Toffoli gate.

The Fredkin gate is a computational circuit suitable for reversible computing, invented by Edward Fredkin. It is universal, which means that any logical or arithmetic operation can be constructed entirely of Fredkin gates. 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.

<span class="mw-page-title-main">Second-order cellular automaton</span> Type of reversible cellular automaton

A second-order cellular automaton is a type of reversible cellular automaton (CA) invented by Edward Fredkin where the state of a cell at time t depends not only on its neighborhood at time t − 1, but also on its state at time t − 2.

<span class="mw-page-title-main">Block cellular automaton</span> Kind of cellular automaton

A block cellular automaton or partitioning cellular automaton is a special kind of cellular automaton in which the lattice of cells is divided into non-overlapping blocks and the transition rule is applied to a whole block at a time rather than a single cell. Block cellular automata are useful for simulations of physical quantities, because it is straightforward to choose transition rules that obey physical constraints such as reversibility and conservation laws.

Unconventional computing is computing by any of a wide range of new or unusual methods. It is also known as alternative computing.

A chemical computer, also called a reaction-diffusion computer, Belousov–Zhabotinsky (BZ) computer, or gooware computer, is an unconventional computer based on a semi-solid chemical "soup" where data are represented by varying concentrations of chemicals. The computations are performed by naturally occurring chemical reactions.

Humans have considered and tried to create non-biological life for at least 3000 years. As seen in tales ranging from Pygmalion to Frankenstein, humanity has long been intrigued by the concept of artificial life.

A quantum cellular automaton (QCA) is an abstract model of quantum computation, devised in analogy to conventional models of cellular automata introduced by John von Neumann. The same name may also refer to quantum dot cellular automata, which are a proposed physical implementation of "classical" cellular automata by exploiting quantum mechanical phenomena. QCA have attracted a lot of attention as a result of its extremely small feature size and its ultra-low power consumption, making it one candidate for replacing CMOS technology.

<span class="mw-page-title-main">Life without Death</span> 2D cellular automaton similar to Conways Game of Life

Life without Death is a cellular automaton, similar to Conway's Game of Life and other Life-like cellular automaton rules. In this cellular automaton, an initial seed pattern grows according to the same rule as in Conway's Game of Life; however, unlike Life, patterns never shrink. The rule was originally considered by Toffoli & Margolus (1987), who called it "Inkspot"; it has also been called "Flakes". In contrast to the more complex patterns that exist within Conway's Game of Life, Life without Death commonly features still life patterns, in which no change occurs, and ladder patterns, that grow in a straight line.

Natural computing, also called natural computation, is a terminology introduced to encompass three classes of methods: 1) those that take inspiration from nature for the development of novel problem-solving techniques; 2) those that are based on the use of computers to synthesize natural phenomena; and 3) those that employ natural materials to compute. The main fields of research that compose these three branches are artificial neural networks, evolutionary algorithms, swarm intelligence, artificial immune systems, fractal geometry, artificial life, DNA computing, and quantum computing, among others.

Norman H. Margolus is a Canadian-American physicist and computer scientist, known for his work on cellular automata and reversible computing. He is a research affiliate with the Computer Science and Artificial Intelligence Laboratory at the Massachusetts Institute of Technology.

<span class="mw-page-title-main">Reversible cellular automaton</span> Cellular automaton that can be run backwards

A reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. That is, it is a regular grid of cells, each containing a state drawn from a finite set of states, with a rule for updating all cells simultaneously based on the states of their neighbors, such that the previous state of any cell before an update can be determined uniquely from the updated states of all the cells. The time-reversed dynamics of a reversible cellular automaton can always be described by another cellular automaton rule, possibly on a much larger neighborhood.

Mictyris guinotae is a species of soldier crab of genus Mictyris, endemic to the Ryukyu Islands of Japan. They were named after Danièle Guinot, a professor at the Muséum national d'histoire naturelle in France, and were first treated as a separate species in a tribute volume to Guinot.

Andrew Adamatzky is a British computer scientist, who is a Director of the Unconventional Computing Laboratory and Professor in Unconventional Computing at the Department of Computer Science and Creative Technology, University of the West of England, Bristol, United Kingdom.

<span class="mw-page-title-main">Critters (cellular automaton)</span>

Critters is a reversible block cellular automaton with similar dynamics to Conway's Game of Life, first described by Tommaso Toffoli and Norman Margolus in 1987.

References

  1. Fredkin, Edward; Toffoli, Tommaso (1982), "Conservative logic", International Journal of Theoretical Physics , 21 (3–4): 219–253, Bibcode:1982IJTP...21..219F, doi:10.1007/BF01857727, MR   0657156, S2CID   37305161 .
  2. Durand-Lose, Jérôme (2002), "Computing inside the billiard ball model", in Adamatzky, Andrew (ed.), Collision-Based Computing, Springer-Verlag, pp. 135–160, doi:10.1007/978-1-4471-0129-1_6, ISBN   978-1-4471-0129-1 .
  3. Margolus, N. (1984), "Physics-like models of computation", Physica D: Nonlinear Phenomena , 10 (1–2): 81–95, Bibcode:1984PhyD...10...81M, doi:10.1016/0167-2789(84)90252-5 . Reprinted in Wolfram, Stephen (1986), Theory and Applications of Cellular Automata, Advanced series on complex systems, vol. 1, World Scientific, pp. 232–246, Bibcode:1986taca.book.....W .
  4. Gunji, Yukio-Pegio; Nishiyama, Yuta; Adamatzky, Andrew (2011), "Robust Soldier Crab Ball Gate", Complex Systems , 20 (2): 93–104, arXiv: 1204.1749 , Bibcode:2012arXiv1204.1749G, doi:10.25088/ComplexSystems.20.2.93, S2CID   14365421 .
  5. Solon, Olivia (April 14, 2012), "Computer Built Using Swarms Of Soldier Crabs", Wired .
  6. Aron, Jacob (April 12, 2012), "Computers powered by swarms of crabs", New Scientist , archived from the original on 2012-04-13.