Laplace’s Demon
Demons and other curiosities
Pierre-Simon Laplace was a French scientist, perhaps one of the greatest ever, French or otherwise. His work affected the way we look at both mathematics and physics, among other areas of science. He may be least known for his discussion of what we now call Laplace’s demon.
Today I want to talk about his demon, and whether predicting the future is possible.
Can we predict the past? Can we predict the present? Can we predict the future? Predicting the past and predicting the present sound a bit silly. The usual question is: Can we predict the future? Although I think predicting the past—if taken to mean “what happened in the past?”—is not so easy.
So can we see the future? I would argue that many can and do very well every day predicting the future. The huge profits of options traders and hedge funds must say something about prediction. They make a lot of money by knowing—at least with some reasonable probability—what the future price will likely be of a stock or commodity.
There are many other predictions that we make that are often correct. We can predict that the sun will rise at tomorrow in Atlanta at 6:54 am. This prediction works very well. The Weather Channel does a reasonable job of predicting the weather for later today, a less good job on tomorrow, and not so good on predicting the weather this calendar day next year.
The issue is not these predictions, but whether it is possible to predict the future exactly. Laplace in 1814 claimed that given the exact position and speed of all objects in the universe at some time a “demon” would be able to use the laws of physics to predict their positions at an arbitrary time in the future. This is now called Laplace’s demon. Translated, he said:
We may regard the present state of the universe as the effect of its past and the cause of its future. An intellect which at a certain moment would know all forces that set nature in motion, and all positions of all items of which nature is composed, if this intellect were also vast enough to submit these data to analysis, it would embrace in a single formula the movements of the greatest bodies of the universe and those of the tiniest atom; for such an intellect nothing would be uncertain and the future just like the past would be present before its eyes.
No Laplace Demon?
Since Laplace’s work there has been much discussion against the idea that even in principle there could be such a demon. Many attacks are now possible. Most are based on ideas and concepts that Laplace did not have available to him in 1814. Chaos theory has been advanced as one way to show hid demon is impossible, the random nature of quantum mechanics is another, and even the natural of computational complexity.
Laplace of course had no idea of the quantum nature of the world. So it is a bit unfair for us to attack him in this way. We could extend Laplace’s intent to a quantum world, noting that quantum mechanics is a deterministic theory even as it describes branching-off worlds. Not all conceivable branches are possible, and we could ask the demon to identify the excluded ones in advance.
We would assume the demon has perfect knowledge of the initial conditions of the universe or of any local Big-Bang event, thus distinguishing our setting from the more human-relevant one in this in-depth essay by Scott Aaronson. Still, it is easier to address Laplace’s argument in the kind of world where Newtonian mechanics holds sway, and where the demon could solve N-body problems exactly even with collisions.
Accordingly, some researchers have looked at the problem of prediction of the future in a Laplacian type world, where the future is deterministic. Not long ago, in 2008, David Wolpert used a riff on Cantor’s diagonalization argument to show that prediction machines could not exist. The latter is one of the reasons that I find the question relevant to theory. His theorem is here and is summarized here:
The theorem’s proof, similar to the results of Gödel’s incompleteness theorem and Turing’s halting problem, relies on a variant of the liar’s paradox—ask Laplace’s demon to predict the following yes/no fact about the future state of the universe: “Will the universe not be one in which your answer to this question is yes?”
A Short Disproof
Recently a short note, called a “Mathbit,” was published by in the Math Monthly by Josef Rukavicka. A Mathbit is always at most a single page and is set in a gray font style.
He claims an even shorter proof that Laplace’s demon is impossible—David’s is more formal and has precise definitions. Here is the main part of Rukavicka’s argument:
Suppose that there is a device that can predict the future. Ask that device what you will do in the evening. Without loss of generality, consider that there are only two options: (1) watch TV or (2) listen to the radio. After the device gives a response, for example, (1) watch TV, you instead listen to the radio on purpose. The device would, therefore, be wrong. No matter what the device says, we are free to choose the other option. This implies that Laplace’s demon cannot exist.
Comments On This Proof
I have several reservations about this proof that there is no Laplace demon. For starters, it assumes a complexity type assumption: that the prediction of the future is fast. What if the prediction of time one day into the future took more than one day? Then of course the argument would fail. Of course this raises an interesting issue. Suppose to predict the future 
This would clearly not allow Rukavicka’s argument to be meaningful.
Another basic issue that struck me is the choice of watching TV vs. radio. Rukavicka assumes implicitly in his argument that we have the free will to decide what to do. But this seems to be the essence of the whole issue. What if we cannot make this choice? We might listen to the predictor say “TV” and tomorrow we forget our contrarian intent to listen to the radio and watch TV anyway. What if we really do not have a choice? This seems to devolve into a circular argument—or am I missing something?
Well these two issues do take the argument back into the realm of Scott’s long essay.
Open Problems
What do you think? In a deterministic world could there be complexity results about predictions? Are these questions related to P=NP in some manner?
“The huge profits of options traders and hedge funds must say something about prediction. They make a lot of money by knowing—at least with some reasonable probability—what the future price will likely be of a stock or commodity. ”
From an Economist review of “The Hedge Fund Mirage: The Illusion of Big Money and Why It’s Too Good To Be True”, by Simon Lack:
“…Of course some investors make a killing, but on average hedge funds have underperformed even risk-free Treasury bills… Why would any client continue to pay for such mediocre returns? One reason is that hedge-fund managers are incredibly good salesmen. In addition, industry insiders who are all too aware of hedge funds’ shortcomings choose not to expose them, Mr Lack argues. Moreover, the common fee structure, in which hedge-fund managers keep 2% of assets as a “management” fee to cover expenses and 20% of profits generated by performance, has made many managers rich, but not their clients… What is worse, the disastrous dive of equity markets in 2008 may have wiped out all the profits that hedge funds have ever generated for investors.”
http://www.economist.com/node/21558231
Compare Laplace’s Demon with Leibniz’s Deity —
☞ The Present Is Big With The Future
Big (I think the Latin was gravis?) as in pregnant.
You might even call this Leibniz’s Law of Universal Gravidation —
If we follow this pregnant line of thought a little further, we next encounter the enlargement operator
of the finite difference calculus, nowadays more often called the shift operator.
In the fullness of time, we come to the logical analogue of differential calculus.
Here is a discussion of how the enlargement operator operates on the example of logical conjunction:
☞ Enlargement Map of Conjunction
Rukavicka’s argument amounts to “suppose we have an unpredictable thing (us), then a device that predicts the future cannot exist”.
more on high freq trading HFT … re a recent influential/ popular book on it by michael lewis etc. … to me the biggest modern disproof of laplace’s demon seems to be the heisenberg uncertainty principle. its a bit of an omission not to mention QM at all in this post. QM revolution has fundamentally (presumably irrevocably) altered the entire paradigm of scientific/ physical determinism …
oh yeah and add to that the more recent conception of dynamical systems, chaotic dynamics and lorentz equation which was a eyeopener and near jawdropper at the time… enjoy the history but dude welcome to the 21st century 😉
oops sorry! that was meant to be lorenz equations. one letter make a lot of difference. see also butterfly effect
What about this version, does it make sense?
“We may regard the present state of the Internet as seen through process calculus. An intellect which at a certain moment would know all channels, and all signals through the channels of which Internet is composed, if this intellect were also vast enough to submit these data to analysis, it would embrace in a single formula the movements of the greatest corporations of the Internet and those of the tiniest individuals; for such an intellect nothing would be uncertain and the future just like the past would be present before its eyes.”
Free will and unpredictability don’t actually figure into Rukavicka’s argument. Nor does time complexity. Suppose Laplace’s demon answered questions either as “yes” or “no”. You could build a machine that says “no” whenever it hears the word “yes” and vice versa. Then you could ask Laplace’s demon, “Will this machine next utter the word “yes?” Then turn on the machine and wait for the answer.
But Rukavicka’s argument just shows that it is impossible to make infallible public pronouncements about the future on demand. Of course that says nothing at all about the possibility of predicting the future.
All that the argument seems to show is that you cannot state predictions of the future with yes/no answers.
Would Laplace’s demon predict quantum mechanics?
Rukavicka’s argument relies on an interaction of the Demon with our universe. It’s like to say that a Laplace Demon, by predicting the position and speed of all particles in a box for any time in future, would next kick the box and break all its predictions.
Therefore, IMO, Rukavicka’s cannot prove that a Demon with no forward interactions on our universe does not exist.
‘What’s Expected Of Us’: a relevant 1-page scifi story by Ted Chiang: http://www.concatenation.org/futures/whatsexpected.pdf
A bit too clever these are. You don’t even need the prediction parts to get someone into trouble once they’ve agreed to answer a question both honestly and with a binary yes/no with no possible third option. (“Is the answer to this question the same as it would have been if I had asked you ‘will you give me all of your money’ instead?”, say.)
“Without loss of generality, consider that there are only two options … No matter what the device says, we are free to choose the other option.”
If we accept this consideration then we have in fact lost some generality. It’s not obvious to me that all we are always free to choose the other option. For example, if the Demon replies, “you will be spending this evening helping your daughter move out of her house which has just this minute flooded,” then you might find that you are not free to choose not to do it.
(I got this insight from Greg Egan, who dramatized it in his novel The Arrows of Time.)
I agree with Gareth that we have in fact lost some generality in this presentation. Consider how, in his example, freedom means responsibility. In other words, if you want to be completely free then be completely responsible. Responsibility is freedom-it just doesn’t look like much fun. The classic example is in the Garden where J’s passion issues forth.
In any case, as Hume remarks, the passions, not reason, motivate our actions.
“I cannot forbear adding to these reasonings an observation,
which may, perhaps be found of some importance. In every
system of morality, which I have hitherto met with, I have always
remark’d, that the author proceeds for some time in the ordinary
way of reasoning, and establishes the being of a God, or
makes observations concerning human affairs; when of a sudden
I am surpriz’d to find, that instead of the usual copulations
of propositions, is, and is not, I meet with no proposition that
is not connected with an ought, or an ought not. This change
is imperceptible; but is, however, of the last consequence. For
as this ought, or ought not, expresses some new relation or
affirmation, ’tis necessary that it shou’d be observ’d and explain’d;
and at the same time that a reason should be given, for what
seems altogether inconceivable, how this new relation can be a
deduction from others, which are entirely different from it.”
Treatise
What we do have is a natural belief in causality. We naturally feel that one billiard ball causes another to move, but that is not an empirically verifiable “idea” and therefore not knowledge (*scientia*). Hume reconciles freedom and necessity in this way.
“But to proceed in this reconciling project with regard to the
question of liberty and necessity; the most contentious question
of metaphysics, the most contentious science; it will not
require many words to prove, that all mankind have ever agreed
in the doctrine of liberty as well as in that of necessity, and that
the whole dispute, in this respect also, has been hitherto merely
verbal… ”
Enquiry
The model of a machine to which questions are posed is not sufficiently general. I don’t think that this argument rules out the possibility that there exists a machine that, given any time/space/velocity coordinates could output a perfect “view” of the universe at those coordinates.
I think there is a flaw in Rukavicka’s argument. If the machine can predict the future, it will know that you will do exactly the opposite whenever the machine’s answer is option (1) or (2). So the machine will lie, answering “you will watch TV”, for example, and then you listen to the radio in the evening. You believe you have free will, however the machine “predicted” the future correctly – and in this case, it is the machine who chose what you should do, saying initially the opposite option.
Rukavicka’s argument makes no sense; it’s the old chestnut of the unstoppable force versus the immovable object. If free will exists, a fully deterministic predictor of the future cannot exist; if there is a fully deterministic predictor of the future, free will cannot exist. As an argument it’s convincing only if you take it as a given that free will exists — we all do out of practical necessity, but that by no means proves it’s real.
The diagonalization argument works because the predictor is part of the universe, and therefore subject to its own predictions. But this argument does not have as big of an impact as Gödel’s: while it was a critical blow to the goals of Bertrand and Russell that formalization couldn’t answer every question, the same is not true for a hypothetical Laplace’s demon. Few people would complain if it was perfect at predicting the stock market but couldn’t handle paradoxical predictions. I don’t know if there would be an interesting (practical) question we would want the answer to that turns out to be undecidable for our demon, the same way there are interesting undecidable problems for Turing machines.
Fortuitously I was thinking about determinism recently and decided to clarify some thoughts on the topic. Principle among these is that from a practical standpoint free will is wedged between classical and quantum intuition on determinism. There are definitely stability bounds we see in our natural world, and the recent measurements of the HIgg’s tell us our vacuum is not nearly as stable as we thought. While we can extrapolate to infinite bounds in order to restore determinism, such extrapolations are unobservable (think about how to construct an observable for “determinism”, not an entirely easy thing to do).
http://thefurloff.com/2014/08/09/obsequity-and-determinism/
I don’t know about constructing quantum observables for determinism, but degrees of determination and measures of determination are studied in the relational programming paradigm.
See, for example, Ali Mili, et al. • Computer Program Construction
Jon,
Indeed, the classical construction of computers can lead to determinism under tight control of the underlying element structure. A Turing machine is certainly the conceptual paradigm for deterministic evolution. I have touched on some of the issues with the non-computability of real functions in the past (see below). Again though, we are always forced to talk in approximations. Even a real computer is only an approximation of an idealized Turing machine. Real machines do not evolve perfectly deterministically…this is trivially proven by random crashing of computers as they become unstable. So again, we are force to a notion of conceptual determinism that can only exist when we take infinite limits.
http://thefurloff.com/2014/02/15/simulation-math-and-the-universe-simple-minds-seek-simple-answers/
I think that in order to simulate something to 100% accuracy, you’d need to account for everything right to the very bottom. In that sense, you’d need something the size of the universe, in order to be able to simulate the universe. It would also have to be independent, which means that within our universe, you won’t be able to access the prediction without inherently throwing it off, since you’d need to account recursively for an infinite number of underlying simulations if you did.
P vs NP is really more about trying to find a needle in an exponential haystack, without having to do an exponential amount of work, so I think it’s really more of a computational boundary problem relating to information, then one about the limits of determinism and knowledge.
Paul.
Paul,
I must gentlemanly disagree about whether P vs NP is related to determinism or not. The question is whether one can of course find an optimal solution as quickly as one can verify it. So if I could build a sufficiently robust model where one could show that the future state of a system is always the optimal solution for a given input state, then having the ability find the solution as quickly as one can verify (e.g. observe) would mean that one could effectively predict the future and practical determinism would exist. In that situation, even though we know that the optimal state is always the solution, our ability to have knowledge of that solution is limited by our ability to compute. Our future state in that sense is still “determined” but our lack of knowledge limits our ability to say anything meaningful about our future state. Our actions would be completely causal, but not predictable. Thus if P=NP in this scenario, we would be able to have complete knowledge of all future times.
This of course is an idealized scenario. I have previous posted some thoughts on the possibility that P=NP practically. In that post I discussed the situation where technical growth grows at such a rate that offsets growth in complexity. I don’t envision that situation to be extendable to infinite bounds, but it does illustrate that technological growth can help us keep pace with ever more complex problems. Entropy is of course the real problem if one where to begin looking at universe scale problems. As energy bleeds into the environment, our ability to grow technically at an exponential rate becomes less and less feasible.
http://thefurloff.com/2014/03/09/moores-law-drives-computational-resources-pnp-practically-part-2/
Rukavicka’s proof assumes that the demon accepts to share his knowledge with us, which is not part of Laplace’s description.
It might very well be that there is a Laplacian demon who can compute what will happen, but since he doesn’t share it with us Rukavicka’s argument can’t be realised. Of course, the demon himself could break his own prediction, so what it really means is that if the demon is part of our universe, and therefore part of the prediction, he doesn’t have free will (and neither do any of us if his predictions are correct).
There’s also the possibility that any computational process – thought processes included – which aims at solving the PvsNP problem is doomed to remain chaotic. This would imply the irrelevance of the concept of truth for P=NP. Indeed, advocates for P!=NP argue that nobody has been able yet to find a polynomial algorithm for 3-SAT, whereas advocates for P=NP reply that such an algorithm hasn’t been proved impossible – the provisional conclusion being, of course, that we’re practically having P!=NP.
An interesting parallel may be drawn here between complexity theory and dynamical systems. Let’s compare 3-SAT with the 3-body problem. The former is hard, the latter is chaotic. On the other hand 2-SAT is polynomial while the 2-body problem is stable. Thus it’s rather tempting to compare the research on PvsNP with the instability of some solar system, or with the unpredictable behavior of all weather simulations.
In chaos theory, the fractal Lorenz attractor is known to possess two lobes and I like to play with the idea that, in complexity theory, they belong to the Lorenz attractor of a thought processes that tries to solve the PvsNP problem. More precisely, they seem to correspond respectively – and in turns – to the alternating opinions that P might, or might not, be equal to NP. When no process can either run a proof nor a disproof, it’s the very notion of truth which vanishes!
It would be interesting to check whether the proof that SAT has the same complexity as 3-SAT isn’t isomorphic to the proof that the n-body problem (n>3) has the same behavior as the 3-body problem. Quite likely also, solving numerically the associated dynamical system is an NP-complete problem for n>=3 and a polynomial problem for n=2.
I wonder if this isomorphism can be pushed any further – that is, identifying the complexity of every computational problem with that of some suitable dynamical system. The same idea seems to work in graph theory, where every computational problem seems to have the same complexity as some suitable graph problem. For example, integer factoring probably has the complexity of graph isomorphism. Also, compare with the well-known fact that every differential n-variety is diffeomorphic to a sub-variety of R↑n…
More on the connection between chaos and complexity. They both have the consequence of making things unpredictable.
You can’t predict the weather because of sensitiveness to initial conditions, and also because of the computational complexity of the weather models involved.
It’s like World War II which was dramatically shortened by Alan Turing when he managed to break the Enigma code. By solving a hard problem in reasonable time, he made the whole war process less chaotic.
So, chaos and complexity seem to work hand in hand to impede our knowledge of the future.
I suggest introducing the principle that “distant future (or distant past) is, on average, always harder to predict than near future (or distant past).” “On average” means that, whenever you manage to predict some future event, you thereby reduce the possibility of predicting some other future events. But if P=NP was proved, that would increase the predictability of almost everything. Thus the whole Universe would have to collapse into a black hole, which is the only safe place where – in my humble opinion – P=NP may hold safely.
In fact a similar diagonalization argument not for an omniscient but an omnipotent being was well known to the scholastic philosophers of the middle ages: “Could an omnipotent being create a stone so heavy that even he could not lift it?” See the wikipedia entry “Omnipotence paradox” for more. So the arguments of Wolpert and Rukavicka are probably nothing new under the sun but anticipated since 800 years.
I wanted to offer a specific response to the argument by Rukavicka. Essentially, the issue is one of stated causality in the argument that is provided. The statement is that the actor is literally responding to the actions of the device. This is a slightly different situation then one of correlation not leading to causation. Here we have an argument that correlation does not evolve from causation (e.g. actor responding to device). So unless one can prove the actions of actor are completely random independently of the assumption of randomness then the above argument devolves into a tautology.
http://thefurloff.com/2014/08/12/laplaces-demon-and-the-anti-correlated-trap/
“Will the universe not be one in which your answer to this question is yes?”
The demon shrugs and says “Sort of.”
As you mentioned in the article, the response time may make the demon’s predictions useless. I submit that the demon can exist, but really precise information about the future that involves human decisions can only be given at the time the other decisions can no longer happen. For example, while waiting for the answer, the person hits the button on the TV remote. In the split second before the button is pressed, but after the action is irreversible, the Demon says “TV.”
• 19th Century Laplace’s Demon integrates trajectories forwards and backwards in time.
• 20th Century Dirac’s S-matrix scatters in-states to out-states via a (bijective, hence reversible) unitary map.
• 21st Century Howard Georgi’s quantum “unparticle” dynamics — see e.g. arXiv:hep-ph/0703260 — messes-up both classical trajectories and quantum S-matrices.
Mother of mercy! Do Georgi’s quantum unparticles portend the end of determinism? And scalable quantum computing too?
Don’t ask me these tough 21st century questions … but GLL readers who care to proffer an opinion are encouraged to post comments either here or on Shtetl Optimized.
———
And in every future, best wishes for an enjoyable August are extended to all readers of Gödel’s Lost Letter and P=NP!
Correction It turns out that the notion of an “S-matrix” was introduced not by Dirac, but rather by none other than a then-young John Archibald Wheeler, in his 1937 article On the Mathematical Description of Light Nuclei by the Method of Resonating Group Structure.
We should all of us hope to still be doing good math, science, and engineering at age 95, like John Wheeler!
One Final Riddle
Which points are closer in time?
• Pierre-Simon Laplace’s death and John Wheeler’s birth? versus
• John Wheeler’s birth and the present date.
No fair Googling!
I think these two papers are relevant to this post:
A Peculiar Connection Between the Axiom of Choice and Predicting the Future
http://hans.math.upenn.edu/~ted/203S10/References/peculiar.pdf
A Proof of Induction?
http://quod.lib.umich.edu/cgi/p/pod/dod-idx/proof-of-induction.pdf?c=phimp;idno=3521354.0007.002
ooo
Thanks for pointers
To give fair credit, I believe that was o0o’s contribution, or possibly oOo (who might be related to ooo, or 000-I don’t know.) In any case, the Kantian inheritance is appreciated. As a gambler, I appreciate the odds of betting on the Axiom of Choice. Do the authors here assert a medium for reliability, as Hume requests, or is this more of a way to reliably function?
Also, am I wrong to recall Hempel’s warning about logical transformations, or Goodman’s “new riddle of induction”?
(Thanks for all the contributions.)
Suppose for simplicity that the demon is outside the universe, and that there is a communication line between us and it. Suppose that the universe is governed by a deterministic law, such classical mechanics and electromagnetism. When ask the demon about what we would do in the evening, it will know exactly what we will do in the evening. The demon will also know that what we will do in the evening might depend on the demon’s answer (It already know that what we were going to ask, but this is not important here). Hence, the demon would want to communicate that knowledge to us as the answer to our question, but we had imposed upon the demon that the answer can only be either yes or no. In other words, if the future of the universe depends on the demon’s action then predicting the future for the demon means producing conditional statements such as “if I do this then the universe will do that”, but not an absolute “the universe will do this, no matter what I do”. Therefore, when we ask the demon what we will do in the evening, we must accept the answer in the form of a function sending “the set of all possible answers” to the set {yes,no}. However, there are problems with this: First, “the set of all possible answers” is clearly an infinite set, so we cannot hope to comprehend all of it before deciding what to do in the evening. Second, this set must include itself as an element, which seems to open up a whole other can of worms.
Small correction: The answer should be in the form of a function sending “the set of all possible answers” to the set {tv,radio}.
What if it is not necessary for there to be a connection between the demon and the universe? For example, in QM the “action at a distance” happens instantaneously and not because of local hidden variables (disproven by Bell’s Theorem and von Neumann’s). So the demon could simply “know” it seems to me
“No matter what the device says, we are free to choose the other option. This implies that Laplace’s demon cannot exist.”
… as long we can predict the past (i.e. we are free to choose the other option if and only if we remember what the device says).
I sympathize with phomer’s point of view.
I think of the universe as one big computer. The best way to simulate it is by using an equally big (and independent) computer. Since that is somewhat difficult to achieve in practice, we need some alternative. We have to use less computation power. Assuming the original computation is not terribly redundant, we need to give way somewhere. The natural choice is to settle for approximate answers, rather than exact ones.
You can modify the argument easily to avoid the free-will assumption.
Consider a machine N that outputs not of its input.
Connect it to the output of Lapace’s demon (D).
Ask D if the output of N will be Yes?
It also avoids the time issue. As long as D is halting its answer will be wrong.
I think the more serious issue is that we assume that we can use D as we please. D may simply refuse to take part in our experiments or might even lie to make its real prediction true. If I were D I would say Yes to you while predicting that the answer will be No.
Your argument is of the same form of the original one. In this case, Laplace’s demon will necessarily be stuck (.i.e. it will never halt). It will be stuck on an infinite recursion since the answer is a function of the answer in itself.
While you can prevent Laplace’s demon from answering correctly, you can not force him into answering incorrectly.
About the short disproof it is clear that can not exist a predictor P able to predict the output of P2 where P2 contains P
The Wolpert proof seems to only show that the demon’s predictions could not involve himself. He must be out of this universe. Did Laplace even place his demon inside the universe, and give him such a strong duty to answer human questions? The short disproof on the other hand merely proves that his interaction with the world (i.e. passing information into the system) would affect that world and change the outcome of his predictions, sometimes, like in the example, making a stable prediction impossible. That seems obvious. However, both proofs place such restrictions on the demon that he becomes equivalent to a god – uninteresting in any practical sense 😉