A billiard ball computer, also known as a conservative logic circuit, is an idealized model of a reversible

Reversible computing

Reversible computing is a model of computing where the computational process to some extent is reversible, i.e., time-invertible. A necessary condition for reversibility of a computational model is that the transition function mapping states to their successors at a given later time should be...

 mechanical computer

Mechanical computer

A mechanical computer is 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 increment output displays...

 based on newtonian dynamics

Newtonian dynamics

In physics, the Newtonian dynamics is understood as the dynamics of a particle or a small body according to Newton's laws of motion.-Mathematical generalizations:...

, proposed in 1982 by Edward Fredkin

Edward Fredkin

Edward Fredkin is an early pioneer of digital physics. In recent work, he uses the term digital philosophy . His primary contributions include his work on reversible computing and cellular automata...

 and Tommaso Toffoli

Tommaso Toffoli

Tommaso Toffoli is a professor of electrical and computer engineering at Boston University. He joined the faculty in 1995. He was born in June, 1943 in Montereale Valcellina, in northeastern Italy, and was raised in Rome. He received his doctorate in physics from the University of Rome La...

. Instead of using electronic signals like a conventional computer

Von Neumann machine

Von Neumann machine may refer to:.* Von Neumann architecture, a conceptual model of a computer architecture* The IAS machine, a computer designed in the 1940s based on von Neuman's design...

, 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.

This model can be used to simulate Boolean circuit

Boolean circuit

A Boolean circuit is a mathematical model of computation used in studying computational complexity theory. Boolean circuits are the main object of study in circuit complexity and are a special kind of circuits; a formal language can be decided by a family of Boolean circuits, one circuit for each...

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

Toffoli gate

In computer science, the Toffoli gate , invented by Tommaso Toffoli, is a universal reversible logic gate, which means that any reversible circuit can be constructed from Toffoli gates...

, from which any other Boolean logic gate may be simulated. Therefore, suitably configured billiard-ball computers may be used to perform any computational task.

It is also possible to simulate billiard ball computers on several types of reversible cellular automaton

Reversible cellular automaton

A reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. Several methods of constructing reversible cellular automata are known, including the block cellular automaton and second-order cellular automaton methods...

, including block cellular automata

Block 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...

 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.