Billiard-ball Computer 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, proposed in 1982 by Edward Fredkin
Edward Fredkin (born October 2, 1934) is a distinguished career professor at Carnegie Mellon University (CMU), and an early pioneer of digital physics.
Fredkin's primary contributions include work on reversible computing and cellular automata. ...
and Tommaso Toffoli. 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.
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 in ...
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 CCNOT 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 "control ...
, 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 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. 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..See also
* Unconventional computing *Fluidics
Fluidics, or fluidic logic, is the use of a fluid to perform analog or digital operations similar to those performed with electronics.
The physical basis of fluidics is pneumatics and hydraulics, based on the theoretical foundation of fluid dyn ...
References
{{reflist Models of computation Mechanical computers Reversible computing