### Collisions

April 6, 2017 When a physics blog presents an article about collisions, one might assume that the topic is classical mechanics, or the statistical mechanics that leads to the thermodynamic behavior of gases. Billiards is a good example of collisions between objects, and there are demonstrations of things such as the conservation of momentum using billiard balls. What's more interesting is the idea that elastic collisions between billiard balls can be used for computation. The idea of a billiard ball computer appears in a 1982 paper by Edward Fredkin and Tommaso Toffoli.[1] Fredkin is noted also for the concept of the Fredkin gate, a logic gate that allows reversible computing. The Fredkin gate is universal, meaning that any logical operation can be done using Fredkin gates. Fredkin was co-inventor, with Marvin Minsky, of the Triadex Muse music synthesizer, a device that produced algorithmic musical sequences based on parameter settings for pitch, volume, and tempo.[2] Fredkin is also a proponent of the interesting concept that the laws of physics actually arise from a simple algorithm that controls the operation of the universe. The complexity of today's universe is explained by the idea that iteration of this simple algorithm has been going on for a long time. I'm reminded of John Wheeler's "It from bit" concept that I wrote about in a previous article (It from Bit, July 8, 2013). Fredkin and Toffoli's fundamental concept was that a computer could be built as a suitably-shaped container filled with an ideal gas, the elastic collisions of the ideal gas molecules, constrained to move within the passages of the container, doing the computation. In an upwardly scaled conceptual model, perfectly elastic billiard balls on a frictionless platform replace the ideal gas molecules. An example billiard ball logic gate is shown in the figure.*A billiard ball implementation of an AND gate, as proposed by Fredkin and Toffoli. When two balls simultaneously enter the gate, their collision results in the ejection of one ball through the output port. It can be seen that synchronization of the input signals is essential to proper operation. (Wikimedia Commons image, modified using Inkscape.)*

Now that we've entered of realm of the "Internet of Things," there are many devices in our homes, offices, and factories that collect data for transmission to a central server. Since many of these devices are battery-powered, or rely on environmental energy-harvesting techniques for power, they transmit infrequently. As an energy-savings measure, they don't listen before transmission, and this leads to another type of collision when two devices transmit data at the same time. The only way that a receiver can handle such a collision is to discard both data streams and obtain the data at a later time when there is no collision. If the transmitting devices are somehow synchronized, as when they are identical devices, started at the same time, and running the same code, their data will just collide at the next transmission time. One way to prevent collision is to have the devices transmit at random intervals; provided, however, that identical devices can be seeded to yield different random sequences. If such devices do transmit at random intervals, how often would collisions occur? Fabian Schneider has published a paper on arXiv that provides some insight into this problem.[3] Schneider has provided equations for determining the probability

**P**of two randomly occurring independent events,

**A**and

**B**, will occur simultaneously when they happen

**n**and

_{A}**n**times in an interval

_{B}**T**and last for periods

**t**and

_{A}**t**. He gives the following example for the process.

_{B}"John works inside his office for 2 hours. A blue car will occur 10 times on the nearby street and remains visible for 1 minute each time. John looks outside 5 times for 3 minutes each. How likely is John going to see a blue car?:Schneider presents an exact solution for the case in which the events,T= 120 min,t= 3 min,_{A}t= 1 min,_{B}n= 5,_{A}n= 10 and we are about to determine_{B}P (120, 3, 1, 5, 10)."[3]

**A**and

**B**, occur just once in the interval, as follows:

He also presents a close approximation of

**P**for any given values of

**n**and

_{A}**n**.

_{B}I tested these results with a computer simulation (C language source code here). For the case of events,

**A**and

**B**, occurring just once in the interval, I got the following result.

*Collision probability as a function of pulse width, for one A and one B pulse of the same width in an interval.The red line shows the predicted values.(Computer simulation data, graphed using Gnumeric.)*

The fit of the equation to the data is superb. For the case in which the events,

**A**and

**B**, occur ten times in the interval, I got the following result.

*Collision probability as a function of pulse width, for ten A pulses and ten B pulses of same width in an interval.The red line shows the predicted values.(Computer simulation data, graphed using Gnumeric.)*

The fit of the data to the second, approximation, equation is also superb.

### References:

- E. Fredkin and T. Toffoli, International Journal of Theoretical Physics, vol. 21, no. 3 (April, 1982), pp. 219-253, doi:10.1007/BF01857727.
- Edward Fredkin and Marvin L Minsky, "Digital music synthesizer," US Patent No. 3,610,801, October 5, 1971.
- Fabian Schneider, "How likely are two independent recurrent events to occur simultaneously during a given time?" arXiv, December 23, 2016

*Permanent Link to this article*

Linked Keywords: Physics; blog; collision; classical mechanics; statistical mechanics; thermodynamic; gas; billiards; conservation of momentum; billiard ball; elastic collision; computation; billiard ball computer; scientific literature; paper; Edward Fredkin; Tommaso Toffoli; Fredkin gate; logic gate; reversible computing; Boolean algebra; logical operation; invention; inventor; Marvin Minsky; Triadex Muse; electronic music synthesizer; algorithmic composition; algorithmic musical sequence; parameter; pitch; loudness; volume; tempo; physical law; laws of physics; algorithm; universe; complexity; Fredkin finite nature hypothesis; iteration; age of the universe; John Archibald Wheeler; It from bit; computer; ideal gas; molecule; computation; conceptual model; friction; AND gate; synchronization; Wikimedia Commons; Inkscape; Internet of Things; home; office; factory; data; data transmission; server; battery-powered; environmental energy-harvesting; radio receiver; bitstream; data stream; randomness; random; random seed; pseudorandom number generator; random sequence; Fabian Schneider; arXiv; equation; probability; approximation; computer simulation; C programming language; source code; collision.c; Gnumeric.

### Google Search

Latest Books by Dev Gualtieri

Thanks to Cory Doctorow of BoingBoing for his favorable review of Secret Codes!

Other Books

- Fizzy Graphene - September 25, 2017

- The First Angiosperm - September 18, 2017

- Noise Thermometry and the Boltzmann Constant - September 11, 2017

- Walking in the Rain - September 4, 2017

- Agitated Atoms - August 28, 2017

- Partial Solar Eclipse at New Jersey - August 24, 2017

- Magnetocapacitive Tunnel Junctions - August 21, 2017

- Tardigrades - August 14, 2017

- Roman Concrete - August 7, 2017

- Solar Spicules - July 31, 2017

- Schroeder Diffuser - July 24, 2017

- Rough Microparticles - July 17, 2017

- Robot Musicians - July 10, 2017

- Walter Noll (1925-2017) - July 6, 2017

- cosmogony - July 3, 2017

- Crystal Prototypes - June 29, 2017

- Voice Synthesis - June 26, 2017

- Refining Germanium - June 22, 2017

- Granular Capillarity - June 19, 2017

- Kirchhoff–Plateau Problem - June 15, 2017

- Self-Assembly - June 12, 2017

- Physics, Math, and Sociology - June 8, 2017

- Graphene from Ethylene - June 5, 2017

- Crystal Alignment Forces - June 1, 2017

- Martian Brickwork - May 29, 2017

- Carbon Nanotube Textile - May 25, 2017

- The Scent of Books - May 22, 2017

- Patterns from Randomness - May 18, 2017

- Terpene - May 15, 2017

- The Physics of Inequality - May 11, 2017

- Asteroid 2015 BZ509 - May 8, 2017

- Fuzzy Fibers - May 4, 2017

- The Sofa Problem - May 1, 2017

- The Wisdom of Composite Crowds - April 27, 2017

- J. Robert Oppenheimer and Black Holes - April 24, 2017

- Modeling Leaf Mass - April 20, 2017

- Easter, Chicks and Eggs - April 13, 2017

- You, Robot - April 10, 2017

- Collisions - April 6, 2017

- Eugene Garfield (1925-2017) - April 3, 2017

- Old Fossils - March 30, 2017

- Levitation - March 27, 2017

- Soybean Graphene - March 23, 2017

- Income Inequality and Geometrical Frustration - March 20, 2017

- Wireless Power - March 16, 2017

- Trilobite Sex - March 13, 2017

- Freezing, Outside-In - March 9, 2017

- Ammonia Synthesis - March 6, 2017

- High Altitude Radiation - March 2, 2017

### Deep Archive

Deep Archive 2006-2008

**Blog Article Directory on a Single Page**