5 ms·

You are correct, sort of. However, there are a number of differential equations where to simulate it requires exponential complexity w.r.t. to the given degree

You are correct, sort of. However, there are a number of differential equations where to simulate it requires exponential complexity w.r.t. to the given degree of accuracy or amount of "time" to simulate it for. For instance, pretty much any chaotic problem.

JadeNB 11y ago
Agreed! There's a reason that non-linear equations are regarded as much harder than linear ones, and I don't mean to gloss over it. However, possibly just because I am a mathematician and not an engineer or hacker, I still find the distinction between "solution that is hard to find" and "no solution" meaningful and important. (It is the difference between "we can't predict the weather" and "there is no such thing as weather"!)
arielby 11y ago
Isn't this exponential precision = polynomial time?
murbard2 11y ago
Oh it's worse than that, decision problems like computing the sign of the solution at a given point are undecidable in general. Yes, you can encode arbitrary Turing machines as differential equations.
- JadeNB 11y ago
  > Yes, you can encode arbitrary Turing machines as differential equations. That's neat! Do you have a reference?
  - murbard2 11y ago
    You can build a physical Turing machine and describe its behavior using Newton's equations of motion, then do a change of variable t -> 1/t. The value at 0 gives you the result of the computation. Q.E.D
    - JadeNB 11y ago
      That's … unsatisfying. I mean that it's unsatisfying in a theoretical sense (because it gives me no theoretical feeling for the Turing-machine-to-differential-equation transformation), but, if I really wanted to be picky, I could point out that (a) nothing in the definition of a Turing machine guarantees its physical realisability (what if its number of states is bigger than the power set of the number of elementary particles in the universe, or, similarly, if it writes on an unbounded amount of tape?), and (b) Newton's equations of motion are only approximations to, not exact descriptions of, the physical universe. Is there any more-or-less explicit recipe that says "given a description of a Turing machine (as a 7-tuple, say https://en.wikipedia.org/wiki/Turing_machine#Formal_definition https://en.wikipedia.org/wiki/Turing_machine#Formal_definiti...), here is a (possibly unmanageably huge) differential equation such that …"—well, I don't even really know what. Your answer suggests that I might ask that, say, the solution $y$ to the differential equation where $y(1)$ somehow encodes a given initial state of the tape is such that $y(0)$ somehow encodes the final state of the tape (with the understanding that $y$ is not defined at $0$ if the machine doesn't halt on the corresponding input).
      - murbard2 11y ago
        Fine, fine, I just think it's an elegant way to say it :) You want something like this http://www.sciencedirect.com/science/article/pii/S1571066108001126 http://www.sciencedirect.com/science/article/pii/S1571066108... or like this http://www.sciencedirect.com/science/article/pii/S019688580700067X http://www.sciencedirect.com/science/article/pii/S0196885807...
        JadeNB 11y ago
        > Fine, fine, I just think it's an elegant way to say it :) You're absolutely right that it's an elegant and compelling argument for the plausibility of the claim; I was just looking for the rigour behind it (even a statement, if not a proof). Your second reference is exactly the sort of thing that I had in mind; thanks!
Gibbon1 11y ago
The classic example is Navier–Stokes equations of viscous fluid flow. True story, one of my college professors handed out a homework assignment that no one could solve. Far as I could tell the boundary conditions described journal bearing that wasn't stable. Such things exist. I think other very hard to deal with are equations where the solution diverges exponentially due to small changes in boundary conditions. Orbital mechanics is like that. Not sure but I can see a situation where the set of equations that describe the solution form a series that never converges to a regular pattern. (irrational series? as irrational numbers but with equations) I think quantum mechanics is like that (Don't quote me)

JadeNB 11y ago

Agreed! There's a reason that non-linear equations are regarded as much harder than linear ones, and I don't mean to gloss over it. However, possibly just because I am a mathematician and not an engineer or hacker, I still find the distinction between "solution that is hard to find" and "no solution" meaningful and important. (It is the difference between "we can't predict the weather" and "there is no such thing as weather"!)

arielby 11y ago

Isn't this exponential precision = polynomial time?

murbard2 11y ago

Oh it's worse than that, decision problems like computing the sign of the solution at a given point are undecidable in general. Yes, you can encode arbitrary Turing machines as differential equations.

JadeNB 11y ago
> Yes, you can encode arbitrary Turing machines as differential equations. That's neat! Do you have a reference?
- murbard2 11y ago
  You can build a physical Turing machine and describe its behavior using Newton's equations of motion, then do a change of variable t -> 1/t. The value at 0 gives you the result of the computation. Q.E.D
  - JadeNB 11y ago
    That's … unsatisfying. I mean that it's unsatisfying in a theoretical sense (because it gives me no theoretical feeling for the Turing-machine-to-differential-equation transformation), but, if I really wanted to be picky, I could point out that (a) nothing in the definition of a Turing machine guarantees its physical realisability (what if its number of states is bigger than the power set of the number of elementary particles in the universe, or, similarly, if it writes on an unbounded amount of tape?), and (b) Newton's equations of motion are only approximations to, not exact descriptions of, the physical universe. Is there any more-or-less explicit recipe that says "given a description of a Turing machine (as a 7-tuple, say https://en.wikipedia.org/wiki/Turing_machine#Formal_definition https://en.wikipedia.org/wiki/Turing_machine#Formal_definiti...), here is a (possibly unmanageably huge) differential equation such that …"—well, I don't even really know what. Your answer suggests that I might ask that, say, the solution $y$ to the differential equation where $y(1)$ somehow encodes a given initial state of the tape is such that $y(0)$ somehow encodes the final state of the tape (with the understanding that $y$ is not defined at $0$ if the machine doesn't halt on the corresponding input).
    - murbard2 11y ago
      Fine, fine, I just think it's an elegant way to say it :) You want something like this http://www.sciencedirect.com/science/article/pii/S1571066108001126 http://www.sciencedirect.com/science/article/pii/S1571066108... or like this http://www.sciencedirect.com/science/article/pii/S019688580700067X http://www.sciencedirect.com/science/article/pii/S0196885807...
      - JadeNB 11y ago
        > Fine, fine, I just think it's an elegant way to say it :) You're absolutely right that it's an elegant and compelling argument for the plausibility of the claim; I was just looking for the rigour behind it (even a statement, if not a proof). Your second reference is exactly the sort of thing that I had in mind; thanks!

Gibbon1 11y ago

The classic example is Navier–Stokes equations of viscous fluid flow. True story, one of my college professors handed out a homework assignment that no one could solve. Far as I could tell the boundary conditions described journal bearing that wasn't stable. Such things exist. I think other very hard to deal with are equations where the solution diverges exponentially due to small changes in boundary conditions. Orbital mechanics is like that. Not sure but I can see a situation where the set of equations that describe the solution form a series that never converges to a regular pattern. (irrational series? as irrational numbers but with equations) I think quantum mechanics is like that (Don't quote me)