Billiard ball computer?qsrc=3044

Fredkin and Toffoli Gate Billiard Ball Model

A billiard ball computer is an idealized model of a computing machine based on Newtonian dynamics. 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, and to provide context to the Halting problem and similar results in computability theory. A paradox seems to arise as a consequence of the existence of this ideal machine, since it shows that there exists no algorithm to predict whether the arbitrary billiard-ball system provides an "output" for any given "input". This leads to an unexpected^[1] conclusion: the question whether a given (moving) object can reach a given position is undecidable under the rules of the Newtonian dynamics.^[2]

The billiard ball model was proposed in 1982 in a seminal paper^[3] of Edward Fredkin and Tommaso Toffoli. The work on this and similar models was continued by the MIT Information Mechanics group and has strong relations with the present Amorphous computing group at MIT or the Quantum Mechanical Hamiltonian Model of Paul Beniof. Presently there are a few research lines related to these kind of models in what it is known as unconventional computing.

When the number of objects (such as billiard balls) in a system becomes large, we need new principles like the entropy or temperature ^[4] relations. And when the multitude of particles are able to react and change (not only in position and momentum) then new behaviours arise. The Amorphous computing paradigm prepares the engineering principles to observe, control, organize, and exploit the coherent and cooperative behaviour of programmable multitudes. The Unconventional ^{[5] [6]} and Biologically-inspired computing paradigms use asynchronous and decentralized agents and include the model of cellular automata. Recent works related to the billiard ball model are the particle-based model ^{[7][8] [9]} and the reaction and diffusion of chemical species ^[10].

See also

• Analog computer
• Biologically inspired computing
• Chemical computer
• Mechanical computer
• Quantum computing
• Reversible computing
• Unconventional computing

References

1. ^ Whewell, William. "The Philosophy of the Inductive Sciences", vol 2. London: John W. Parker. 1847, pages 274-295
2. ^ Adamatzky, Andrew (Ed.) "Collision-based Computing". Springer. 2002
3. ^ Fredkin, Edward and Toffoli, Tomasso, "Conservative Logic", Int. J. Theor. Phys. 21 (1982), 219-253. Describes the Billiard-Ball model.
4. ^ Unconventional computation Conference 2007 , http://cnls.lanl.gov/uc07/
5. ^ Information Mechanics and Unconventional computating, http://www.interquanta.biz/im/
6. ^ "Particle-based Methodology for Representing Mobile Ad-Hoc Networks", InterSense 2006 Conference Nice ACM Press New York
7. ^ "Special issue on particle based modelling methods applied in biology", Issue 7 May 2001, ACM
8. ^ "Physics-Based Models to Support Test and Evaluation, S. Blankenship & F. Mello, High Performance Computing Workshop 1998" http://www.dtc.army.mil/hpcw/1998/blanken/blanken.html
9. ^ the Gray-Scott model of a chemical reaction. http://www-swiss.ai.mit.edu/projects/amorphous/GrayScott/ja:ビリヤードボール・コンピュータ