9
$\begingroup$

Well-known examples of computation inspired by natural phenomenon are quantum computers and DNA computers.

What is known about the potential and/or limitations of computing with Maxwell's laws or gravity?

That is, incorporating nature's "quick" solutions to Maxwell's equations or the n-body problem directly into a general-purpose algorithm?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ I think they have actually built computers that use gravity: en.wikipedia.org/wiki/MONIAC_Computer :) $\endgroup$
    – Jukka Suomela
    Feb 13, 2011 at 17:23
  • $\begingroup$ Fluidic logic... interesting $\endgroup$
    – user3804
    Feb 14, 2011 at 4:16
  • 1
    $\begingroup$ Incidentally, I'd be a bit cautious of the extremes. For instance, it seems that taken in isolation, general relativity may allow for computations beyond those we can do with classical models. However, for a "natural" solution, we cannot ignore the rest of what we know about physics: The black hole computer I outlined below conflicts with thermodynamics and quantum mechanics. Any good solution to computing with fundamental forces should probably lie in the intersection of our physical theories. (I'd say that quantum computing qualifies, here.) $\endgroup$
    – funkstar
    Feb 17, 2011 at 9:14

5 Answers 5

Reset to default
11
$\begingroup$

It's not clear what an "algorithm" based on natural forces implies. Arguably, a quantum computer already operates based on 'natural principles' (excluding gravity, but including Maxwell's equations). What are the atomic steps in your 'natural algorithm' ? If you're talking about taking an $n$-body system and letting it "evolve" to perform a computation, how would you measure its running time ?

Along these lines though, Roger Brockett did some interesting work in the 80s on viewing sorting and linear programming as the solution to a dynamical system.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, your comments help me understand some of the conceptual issues. And the Brockett paper looks very interesting. $\endgroup$
    – user3804
    Feb 14, 2011 at 4:32
  • $\begingroup$ Of course, adiabatic quantum computing doesn't easily fit in the paradigm of "a sequence of elementary operations" either... $\endgroup$
    – Niel de Beaudrap
    Dec 2, 2012 at 13:11
13
$\begingroup$

At present, quantum computation is the most powerful of computational model based on known physics to have been experimentally realised, and can efficiently simulate Maxwell's equations, and pretty much every other physical phenomenon you encounter in day to day life. As the others have mentioned, one exception to this is general spacetimes allowed as solutions in general relativity.

There has been quite a lot of interest in the computational power of computers with access to closed time like curves, for example. However there is absolutely no evidence that these exist in nature or that they can be created artificially. So, while there are potentially interesting computational models that incorporate general relativity in some form, there is significant doubt over whether such models can be realised, and before we can have the most general model of physical computation we need a solid theory of quantum gravity.

Further the interesting features of general relativity tend to only show up in regions of high curvature, which is very different from the almost flat region of spacetime we inhabit and the effects of relativity in such flat(ish) space offer no computational advantage.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ but of course we'll be planting our supercomputers in a black hole ;) $\endgroup$
    – Suresh Venkat
    Feb 13, 2011 at 16:54
10
$\begingroup$

For gravity, there has been some interest in "relativistic computing" which uses the structure of spacetime to speed up computations in some way. Some ideas include the Malament-Hogarth Spacetime and computing via black holes: Start your computer with a computation to, say, decide the Goldbach conjecture (by looking for a counterexample) and then throw yourself into a black hole. Infinite time can pass for the computer outside the hole to look for a counterexample, but this is only experienced as finite time for you inside, so if you don't receive a signal with a counterexample by some deadline you "know" that none exists.

You might also be interested in the Physics and Computation Workshop.

Improve this answer
$\endgroup$
1
2
$\begingroup$

Here's one interpretation of your question, which you may or may not have intended, but for which I have an answer.

Computers are obviously real physical devices and therefore can be modeled by the laws of physics. But we don't use the laws of physics that would be needed to describe a real computer as a model of computation because it's too complex. To make a model of computation, we define something like a Turing machine that is simple enough to be mathematically tractable. However, now we've untethered the model from the physical world, because we don't say how the Turing machine is built or what forces drive it to run.

So can we devise some simple models that capture "computation", but whose fundamental rules are physical in nature? My answer to this would be to check out the Feynman Lectures on Computation: http://www.amazon.com/Feynman-Lectures-Computation-Richard-P/dp/0738202967

He talks about a lot of different simple physical systems that carry out a computation. For example, there is the billiard ball model of Fredkin and Toffoli (http://en.wikipedia.org/wiki/Billiard-ball_computer), where the point was to explicitly account for energy requirements and to design a computer that can run for arbitrarily many steps for arbitrarily little energy. In particular, the chapter on reversible computing has a lot of these kinds of examples.

We think about this issue a lot in my lab. For example, we've done some work on what it means for chemical reaction networks to do computation: http://www.dna.caltech.edu/DNAresearch_publications.html#DeterministicCRNs and http://www.dna.caltech.edu/DNAresearch_publications.html#ComputationalCRNs

We also think about how seeded crystal formation can carry out computation: http://www.dna.caltech.edu/DNAresearch_publications.html#Simulations as well as actually trying to make it happen experimentally: http://www.dna.caltech.edu/DNAresearch_publications.html#OrigamiSeed, and some other work based on computing using a physical phenomenon called DNA strand displacement: http://www.dna.caltech.edu/DNAresearch_publications.html#DNALogicCircuits

Improve this answer
$\endgroup$
0
$\begingroup$

Quantum theory captures the concept of discrete objects pretty well. Other physics theories don't.

Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ I'm not really sure how accurate this is. Certainly quantum theory allows for a certain level of natural discretization, but this can also be present in classical physics (i.e. a bit of string is either connected or broken, a potential can have a finite number of minima, etc). If anything quantum physics makes things more continuous, by allowing continuous evolution between orthogonal states. $\endgroup$
    – Joe Fitzsimons
    Feb 16, 2011 at 12:15
  • $\begingroup$ Evolution is identical in quantum and classic theories -- Hamiltonian dynamics. It is the state that differs. Certainly there are [applied] physics fields where one could model binary gates. The question is if anything within framework of fundamental classic theories (such as gravity,electromagnetism) can give rise to discrete states. $\endgroup$
    – Tegiri Nenashi
    Feb 16, 2011 at 18:13
  • $\begingroup$ The fact that quantum mechanics also has a Hamiltonian does not mean that the dynamics are identical. The Hamiltonians are simply not the same (you need to quantize the classical Hamiltonian). This gives rise to different dynamics. Classical physics can equally give rise to such discrete sets: the presence or absence of a particle (say, an electron) in a particular spatial mode. Double well potentials are a really simple example of this. At zero temperature the particle in the well is in one of 2 states. Further, relativity does a wonderful job of partitioning spacetime. $\endgroup$
    – Joe Fitzsimons
    Feb 16, 2011 at 18:29
  • $\begingroup$ I won't argue against local minima of continuous function interpreted as discrete states. All it takes to manufacture transistor/vacuum tube (and, therefore, logic gate) is putting some control potential over the flow of electrons; entirely within the realm of classic physics. I'd suggest that if you want to model some CS artifacts -- the most notorious being infinite set of natural numbers -- quantum mechanics readily provides you with such. $\endgroup$
    – Tegiri Nenashi
    Feb 16, 2011 at 21:21
  • 2
    $\begingroup$ The number of standing modes of a wave in a cavity is also a countable infinity. This really isn't the benefit of quantum computing. $\endgroup$
    – Joe Fitzsimons
    Feb 16, 2011 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.