Billiard Ball Computing on:
[Wikipedia]
[Google]
[Amazon]
A billiard-ball computer, a type of conservative logic circuit, is an idealized model of a reversible
A billiard-ball computer, a type of conservative logic circuit, is an idealized model of a reversible mechanical computer
A mechanical computer is a computer built from mechanical components such as levers and gears rather than electronic components. The most common examples are adding machines and mechanical counters, which use the turning of gears to incremen ...
based on Newtonian dynamics
In physics, Newtonian dynamics (also known as Newtonian mechanics) is the study of the dynamics of a particle or a small body according to Newton's laws of motion.
Mathematical generalizations
Typically, the Newtonian dynamics occurs in a thre ...
, proposed in 1982 by Edward Fredkin
Edward Fredkin (October 2, 1934 – June 13, 2023) was an American computer scientist, physicist and businessman who was an early pioneer of digital physics.
Fredkin's primary contributions included work on reversible computing and cellular au ...
and Tommaso Toffoli
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 (with Edward Fredkin and othe ...
. Instead of using electronic signals like a conventional computer
A computer is a machine that can be Computer programming, programmed to automatically Execution (computing), carry out sequences of arithmetic or logical operations (''computation''). Modern digital electronic computers can perform generic set ...
, it relies on the motion of spherical billiard ball
A billiard ball is a small, hard ball used in cue sports, such as carom billiards, pool, and snooker. The number, type, diameter, color, and pattern of the balls differ depending upon the specific game being played. Various particular ball pro ...
s 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.
Simulating circuits with billiard balls
This model can be used to simulateBoolean circuit
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible inpu ...
s 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
In logic circuits, the Toffoli gate, also known as the CCNOT gate (“controlled-controlled-not”), invented by Tommaso Toffoli in 1980 is a CNOT gate with two control bits and one target bit. That is, the target bit (third bit) will be inver ...
, from which any other Boolean logic gate may be simulated. Therefore, suitably configured billiard-ball computers may be used to perform any computational task.
Simulating billiard balls in other models of computation
It is possible to simulate billiard-ball computers on several types ofreversible cellular automaton
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 s ...
, 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.
Logic gates based on billiard-ball computer designs have also been made to operate using live soldier crabs of the species ''Mictyris guinotae
''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 ...
'' in place of the billiard balls..
See also
*Unconventional computing
Unconventional computing (also known as alternative computing or nonstandard computation) is computing by any of a wide range of new or unusual methods.
The term ''unconventional computation'' was coined by Cristian S. Calude and John Casti an ...
* Fluidics
Fluidics, or fluidic logic, is the use of a fluid to perform analog signal, analog or Digital data, digital operations similar to those performed with electronics.
The physical basis of fluidics is pneumatics and hydraulics, based on the theore ...
References
{{reflist Models of computation Mechanical computers Reversible computing