“Billiard-ball computer”的意思、由来-开放百科全书

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.

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]

References

1. ^{{citation | last1 = Fredkin | first1 = Edward | author1-link = Edward Fredkin | last2 = Toffoli | first2 = Tommaso | author2-link = Tommaso Toffoli | doi = 10.1007/BF01857727 | issue = 3-4 | journal = International Journal of Theoretical Physics | mr = 657156 | pages = 219–253 | title = Conservative logic | volume = 21 | year = 1982|bibcode = 1982IJTP...21..219F }}.
2. ^{{citation|first=Jérôme|last=Durand-Lose|contribution=Computing inside the billiard ball model|title=Collision-Based Computing|editor-first=Andrew|editor-last=Adamatzky|editor-link=Andrew Adamatzky|publisher=Springer-Verlag|year=2002|pages=135–160|isbn=978-1-4471-0129-1}}.
3. ^{{citation | last = Margolus | first = N. | author-link = Norman Margolus | doi = 10.1016/0167-2789(84)90252-5 | journal = Physica D: Nonlinear Phenomena | pages = 81–95 | title = Physics-like models of computation | volume = 10 | year = 1984|bibcode = 1984PhyD...10...81M }}. Reprinted in {{citation | last = Wolfram | first = Stephen | author-link = Stephen Wolfram | pages = 232–246 | publisher = World Scientific | series = Advanced series on complex systems | title = Theory and Applications of Cellular Automata | volume = 1 | year = 1986}}.
4. ^{{citation | last1 = Gunji | first1 = Yukio-Pegio | last2 = Nishiyama | first2 = Yuta | last3 = Adamatzky | first3 = Andrew | author3-link = Andrew Adamatzky | arxiv = 1204.1749 | journal = Complex Systems | issue = 2 | pages = 93–104 | title = Robust Soldier Crab Ball Gate | url = http://www.complex-systems.com/abstracts/v20_i02_a02.html | volume = 20 | year = 2011|bibcode = 2012arXiv1204.1749G }}.
5. ^{{citation|url=https://www.wired.com/wiredenterprise/2012/04/soldier-crabs/|journal=Wired|first=Olivia|last=Solon|date=April 14, 2012|title=Computer Built Using Swarms Of Soldier Crabs}}.
6. ^{{citation |first=Jacob|last=Aron |date=April 12, 2012 |title=Computers powered by swarms of crabs |journal=New Scientist |url=https://www.newscientist.com/blogs/onepercent/2012/04/researchers-build-crab-powered.html|archive-url=https://web.archive.org/web/20120413072249/https://www.newscientist.com/blogs/onepercent/2012/04/researchers-build-crab-powered.html|archive-date=2012-04-13|dead-url=yes}}.