5 ms·
Using physical space and particle interactions for solving computational problems seems like such an elegant hack. Proteins fold and chemistry just works in 3D
by echelon 10y ago
Using physical space and particle interactions for solving computational problems seems like such an elegant hack. Proteins fold and chemistry just works in 3D space, yet we have problem computing these things. I wonder why we don't do more computing on the physical fabric of the universe itself. It seems like an optimally efficient tool for problem solving.
Are there any other approaches along this same vein? It's incredibly fascinating.
- yablak 10y agoBefore computers had the kind of processing power they do now, engineers would build analog circuits to solve differential equations. A modern-day quick link: http://www.dummies.com/education/science/science-electronics/how-to-solve-differential-equations-using-op-amps/ http://www.dummies.com/education/science/science-electronics...
- yablak 10y ago(nowadays it's usually the other way around, of course ;)
- versteegen 10y agoBefore electronic computers existed, engineers built mechanical analog devices called differential analysers [1] to compute derivatives and integrals, invented in 1876 by brothers James Thomson and Lord Kelvin. Famously, cheap differential analysers were built out of Meccano starting in 1934 [2]. After scientists gained access to electronic computers, these old analysers were repeatedly handed down through lower-budget institutions, schools and eventually museums. [1] https://en.wikipedia.org/wiki/Differential_analyser https://en.wikipedia.org/wiki/Differential_analyser [2] http://amg.nzfmm.co.nz/differential_analyser_explained.html http://amg.nzfmm.co.nz/differential_analyser_explained.html
- Sharlin 10y agoThis old US Navy training film on mechanical fire control calculators (called "computers" back then, used to calculate firing solutions on warships) is pretty fascinating: https://www.youtube.com/watch?v=s1i-dnAH9Y4 https://www.youtube.com/watch?v=s1i-dnAH9Y4
- SilasX 10y agoAlso like sleep sort, something else -- some other real resource -- still has to bear the asymptotic cost of the algorithm. In this case, AIUI, you have to pay in "light distance traveled", which goes up exponentially with the problem size.
- gizmo686 10y agoBut going to physical processes could change the asymptotic cost by adding new primitives. There is the Computational Complexity-Theoretic Church–Turing Thesis, which hypothesis that any physical model of computation can be efficiently (eg. in polynomial time) be simulated by a turing machine. This has never been proven, but it has led to correct physical predictions so far. We also have have demonstrated polynomial improvement that can be had by moving away of a turing machine. For example, the use of random access memory offers an asymptotic improvement for many algorithms relative to the linear access memory used by a turing machine. Additionally, Grover's algorithm allows an exponential speed up in a wide range of problems on a quantom computer; and neither of these approaches requires shifting the savingns onto some other resource.
- SilasX 10y agoRandom access just assumes you can instantly jump to a memory location. In any physical instantiation, you're still limited in how quickly you can access by the speed of light. (It's true that you can pack the memory into a 3D volume and thus have a cubic improvement in access time, but you can do the same thing with a multi-dimensional TM.)
- cmrx64 10y agoNote: nitpicking follows :) RAM machines are an abstraction, there's no such thing as constant-time access to a random address in any physical store. At best you're looking at O(n^0.5) where n is the number of bits in the store. Still a speedup, but not nearly as much as predicted by using a RAM machine. Grover's algorithm doesn't offer exponential speedup over classical algorithms, its complexity is O(n^0.5) queries, where n the size of the list being searched, versus O(n) queries classically.
- taneq 10y agoWell, there's spaghetti sort: https://en.wikipedia.org/wiki/Spaghetti_sort https://en.wikipedia.org/wiki/Spaghetti_sort Also things like using slime mold to solve the traveling salesman problem: http://phys.org/news/2013-03-blob-salesman.html http://phys.org/news/2013-03-blob-salesman.html And if you want to go simpler, there's always mechanical analog computers: https://youtu.be/s1i-dnAH9Y4 https://youtu.be/s1i-dnAH9Y4 (it's long but well worth a watch IMO) Oh, and obviously anything involving a scale model, especially for fluid dynamics (so wind tunnels, wave tanks etc), is doing the same thing in spirit.
- hackcasual 10y agoSlime molds aren't guaranteed to find optimal solutions
- zdkl 10y agoYou'll have to break out "Moldy Carlo" simulations for that!
- saurik 10y agoThat analysis of spaghetti sort is incorrect as you scale N to a size larger than the hand. It will take time linear in the number of straws to move your hand across the tips to find the largest one, and this will be true for any size hand as no matter how large the hand is, there is an upper limit to the number of straws it can hover over in parallel. One of the big points of complexity analysis is that at small scales you might see certain behavior but what we are really interested in is asymptotic complexity: this is like saying selecting the lowest value from an unsorted array is faster than a tree iif the array has so few entries that it fits into the L1 cache (while the tree's randomly scattered memory means walking its left edge could take much longer; essentially making the array O(1) in memory accesses while the tree is O(log n)). A better analysis of spaghetti sort should find it to be O(n^2), if the algorithm really continues to function at all (and it isn't clear to me that it correctly scales). (It is also worth nothing that if you want a limited purpose linear time sorting algorithm based on the same "let's change the notion of comparison", we even have working ones that function on real world computers: radix sort is insanely epic and with a little assistance from insertion sort fix up passes I have used it to sort Unicode strings in seemingly impossibly fast times.)
- IIAOPSW 10y ago>I wonder why we don't do more computing on the physical fabric of the universe itself. It seems like an optimally efficient tool for problem solving. Are there any other approaches along this same vein? you literally just described the origin of quantum computing.
- rainforest 10y agoSomeone has described using a physical network to solve the shortest-path problem in O(N) time: https://www.reddit.com/r/compsci/comments/a1sqb/help_shortest_distance_algorithm_on_a_very_large/c0fg9lr https://www.reddit.com/r/compsci/comments/a1sqb/help_shortes...
- cauterized 10y agoThat doesn't seem right to me. You'd have to tie a string between every single possible pair of nodes, so it's O(N^2).
- jameshart 10y agoThe wiffle-ball-graph data structure is O(n) for insertion, sure (each new ball has to be tied to a bunch of existing balls and finding them is probably O(n) at best), so building an n-node wiffle-graph is O(n^2), but shortest path queries on the data structure are O(n) at any time (again because you have to go find the two nodes of interest, then spread them apart by at most n units of distance). You can also sort all the nodes by distance from any given node in O(n) time by holding the chosen wiffle ball and hanging the graph over the edge of an O(n) tall tower.
- deleted 10y ago[deleted]
- versteegen 10y agoI'm reminded of Bead Sort [1], which is an amusing physical sorting algorithm for integers represented in unary. The sorting can be done in O(sqrt(n)) time (time taken for the beads to fall under gravity; n is input size in unary), but that doesn't include the time needed to load the input and read the result. [1] https://en.wikipedia.org/wiki/Bead_sort https://en.wikipedia.org/wiki/Bead_sort
- dharma1 10y agoThis paper describes an optical implementation to some transforms used in deep learning http://arxiv.org/abs/1511.05946 http://arxiv.org/abs/1511.05946 These guys use optical computing for big data analysis and pattern matching http://optalysys.com/ http://optalysys.com/
- nolite 10y agoThis is what DWave really does when it comes down to it (if you ignore all the back and forth on whether it is or is t a quantum computer) Also there's the usage of passing laser light through lenses to implement Fourier transforms
- amelius 10y ago> I wonder why we don't do more computing on the physical fabric of the universe itself. It seems like an optimally efficient tool for problem solving. I think in many cases it is much simpler to perform simulations rather than run the actual physical experiment.
- azeirah 10y agoChemical computing comes to mind Video: https://www.youtube.com/watch?v=cHoYNStQOEc https://www.youtube.com/watch?v=cHoYNStQOEc (not by an orignal author) Paper: http://link.springer.com/chapter/10.1007/11527800_2 http://link.springer.com/chapter/10.1007/11527800_2 More stuff: https://github.com/gigasquid/chemical-computing https://github.com/gigasquid/chemical-computing
- hammock 10y agoInterestingly, the physical-space algorithms proposed in child comments are only two-dimensional (spaghetti sort, bead sort). Granted, they do take a one-dimensional problem and solve it in a higher dimension. Would be fascinated to see something even higher, for example, traveling salesman problem solved in 3D space.
- j-pb 10y ago>I wonder why we don't do more computing on the physical fabric of the universe itself. Could you explain how a regular old computer is not doing exactly that? The last time I checkt it had quite a bit of physics going on.
- hammock 10y agoI'm reminded of a recent front page submission, this large-scale physical model of the Mississippi River that was built for use in flood planning. https://news.ycombinator.com/item?id=12163592 https://news.ycombinator.com/item?id=12163592