Lecture
Billiard-ball computer (English: Billiard-ball computer) — a logical model for performing reversible computation, a mechanical computer based on Newton's laws of motion and proposed in 1982 by Edward Fredkin[en] and Tommaso Toffoli[en] .
Instead of using electronic signals, as in an ordinary von Neumann architecture computer, it applies the principles of motion of billiard balls in the absence of friction. The billiard-ball computer can be used to study the connections between reversible computation and reversible processes in physics.
The billiard-ball computer models Boolean logic circuits, using, instead of wires, paths along which balls move, bounded by walls: the signal is encoded by the presence or absence of balls on the paths, and logic gates are modelled by means of collisions of balls at the intersections of paths. In particular, the paths of the balls can be arranged so as to obtain a Toffoli gate, a universal reversible logic gate, by means of which any other reversible logic gate can be obtained. This means that a properly arranged billiard-ball computer is capable of performing any computation .
A billiard ball Fredkin and Toffoli gate, a model of an AND logic element. When a single billiard ball enters the gate through input 0-in or 1-in, it passes through the device unobstructed and exits through 0-out or 1-out. However, if a 0-ball arrives at the same time as a 1-ball, they collide with each other in the upper left corner of the device and redirect each other so as to collide again in the lower right corner of the device. Then one ball exits through 1-out, and the other ball exits through the lower AND output.. Thus, the presence of a ball emitted from the AND output is logically consistent with the output of an AND logic element, which takes the presence of a ball at 0 and 1 in as its input data.
The billiard-ball computer can be simulated using various types of reversible cellular automata, including block automata and second-order automata. In such models, the balls move at a constant speed along the coordinate axes, which is enough to simulate logic circuits. Both the balls and the walls correspond to certain groups of live (containing 1) cells, and the surrounding field is filled with dead (containing 0) cells .
The billiard-ball computer can also be implemented using live soldier crabs of the species Mictyris guinotae as the billiard balls.
The following applies to computers that use similar principles but are not necessarily reversible.
Kobe University and the University of the West of England , in studying billiard balls, found that instead of a ball there are things that have been implemented with a crab-based logic gate . The crab used in the Iriomote experiment, living in the mictyris brevidactylus relative (Mictyris guinotae in), is known in English as the soldier crab, and has the habit of moving in the same direction as the herd. Logical operations can be performed using the fact that direction is fixed when groups of crabs collide and merge. The computation is carried out by simultaneously herding the swarm toward an intersection formed by a partition. The result of the computation can be seen by which end of the intersection the crabs reach.
Principles analogous to those of billiard-ball computers, such as the collision of objects, are used to implement logical operations in the world of sandbox games, such as Minecraft, and in software for building game maps, such as Super Mario Maker.
Comments