- More Really is Different
By Mile Gu, Christian Weedbrook, Alvaro Perales, Michael A. Nielsen
arXiv:0809.0151v1 [cond-mat.other]
Abstract: In 1972, P.W.Anderson suggested that `More is Different', meaning that complex physical systems may exhibit behavior that cannot be understood only in terms of the laws governing their microscopic constituents. We strengthen this claim by proving that many macroscopic observable properties of a simple class of physical systems (the infinite periodic Ising lattice) cannot in general be derived from a microscopic description. This provides evidence that emergent behavior occurs in such systems, and indicates that even if a `theory of everything' governing all microscopic interactions were discovered, the understanding of macroscopic order is likely to require additional insights.
Since Stephen Luttrell asked last week what I think about the paper, I thought I should come back to it.
The paper is really neat. Here is a quick summary. The authors consider a 2-dimensional spin lattice with nearest neighbor interaction. We thus have a lattice of ups and downs that can influence the other ups and downs around them according to some rule given by the Hamiltonian of the system. On this lattice, the authors put certain “designer Ising blocks” with an associated Hamiltonian, composed of several spin states. These blocks have the property that if they are in the ground state (the state of lowest energy), and one forces the spins on one side to be in a certain pattern of ups and downs by applying a field, then the other side will produce a certain output. They give specific examples in the appendix.
If one covers a 2-dimensional semi-infinite plane with these blocks and has an input on one side of the first row, the spin-spin interactions give a rule determining what is on the other side of that row, which is the input for the second row. And so on. Thus, the ground state of the system is fully determined. But what can we say about this ground state?
Now here is the clue of the paper. The authors show that with the appropriate initialization and designer blocks, one can map a cellular automaton to this spin-system. A cellular automaton operates on a one dimensional input line according to a specific rule. This rule crates a new state, on which the rule is applied again etc. This is commonly shown in a diagram with all the so created states below each other, each corresponding to a certain time step. In the spin-lattice, there are no time steps, but the ground state would be a picture of these states of the cellular automaton. Note however that for the spin-lattice this is not a time-dependent realization of this state. The ground-state just is specified according to some rules.
However, there exists cellular automata for which it can be proven that no non-trivial questions can be answered about their evolution, without actually running them and looking, thus one can never say anything about the total evolution. Because of the correspondence to the spin-lattice this then means there are questions about its ground state that can't be answered either. An example for such a question would be what the overall magnetization is of the system. There is thus no way to derive this quantity from the Hamiltonian, the question is undecidable.
It should be noted that it is important for this conclusion the spin-lattice is indeed infinite. The approximation that a system is infinite is very common in physics and often used to simplify computations. What this argument thus shows is that in this limit, there can remain questions open that fundamentally can not be answered about the whole system.
The title of the paper is a reference to Anderson's paper “More is Different,” an argument against reductionism, claiming that not every system can be understood by merely analysing its parts. Gu et al's paper provides an explicit example for which it can be proved that it indeed is not possible to understand the whole system from the behavior of its constituents. For this argument to hold however “more” isn't enough, it has to be infinitely more.
On the risk of merely expressing my utter ignorance, this doesn't surprise me much. What the authors have shown in the paper is a map from a cellular automata, commonly run on a computer, to a 2-d spin lattice. This lattice is a physical realization of a computer code and thus similar conclusions hold for both. As far as I am concerned, if I run the code and visualize it on my screen (for an infinitely long time of course) this is also a physical realization of the code, it is a state my computer's hardware is in. However, the map to the spin system is without doubt much cleaner and better to analyze.
It would be interesting to see whether one could find a possibly weaker statement for large, but finite systems.
For more on the topic, see also my post Emergence and Reductionism, NewScientist's article Why nature can't be reduced to mathematical laws, or check out Stuart Kauffman's last week talk The Open Universe: Toward a Post-Reductionist Science, PIRSA:08100058.
Mile Gu, Christian Weedbrook, Alvaro Perales, Michael A. Nielsen (2008). More Really is Different arXiv
Physics embraces intensive properties and quantities (temperature, pressure) while disdaining extensive properties and quantities where what you get depends upon how much you have. If the universe patronizes emergent properties, physics is heuristics.
ReplyDeletePythagoreans suffered irrational numbers. Whitehead and Russell Principia Mathematica suffered Kurt Gödel. When theory arises from deep symmetries while observables arise from symmetry breakings, theory is deficient. Get over it and get on with it.
Hi Bee,
ReplyDelete“What this argument thus shows is that in this limit, there can remain questions open that fundamentally can not be answered about the whole system.”
The Penrose argument would be the test of what comprises as being knowable is not decided by saying it only represents things that are computable as it is commonly considered. The trick of course is to somehow consider all at once, where time is not a factor.
From this perspective there is a distinction to be made between an outcome being determinable rather then computable when the system being considered is infinite. This of course is how Penrose considers what arises from consciousness as apposed to what is or can be simply computed.
The question it provokes is to ask if the universe is simply a program that is running oblivious to result or rather outcome(s) being enacted which have been beforehand decided? For me it is like asking if the last digit of PI must be known before a circle can form or is it enough for nature that economy when decided constitutes to form only one outcome?
Best,
Phil
Dear Bee,
ReplyDeleteThanks for the pointer to that arxiv article - it actually resonates much with the spirit of what I am looking at at the moment, which is not particle-particle interactions but more related to bulk matter materials science - though nonetheless inspired by more fundamental considerations, albeit extended in a nonobvious manner.
I still am a fan of reductionism though, in the restricted sense that I still am really only interested with theories that deal with a local description of a physical system. Engineering applications are hard to implement after all if one cannot ultimately write down a system of equations to solve.
Best Regards,
Tumbledried
Dear Bee,
ReplyDeleteIs the argument that this Ising system is a Turing machine, and ability to compute the ground state is equivalent to solving the halting problem?
I really ought to look it up for myself; but since you wrote about it....
:)
-Arun
This seems related ( and neglected)
ReplyDeletehttp://www.ph.biu.ac.il/data/papers/26/201.pdf
Dear Bee,
ReplyDeletethanks for pointing out this interesting paper :-)
But I have to admit, after reading through it, that I a'not so sure what to make of the result.
When I've understood it correctly, an important point of the argument (though not discussed explicitely) is that one has to fix the couplings between neighbouring spins in a very special way, so that indeed the ground state corresponds to the solution of the cellular automaton.
Using a standard (and homogenous)ferromagnetic Ising coupling wouldn't work.
But then, one is dealing with a kind of special Ising spin glass, with very specific local couplings, and has indeed a very complex system - with complexity hidden in the distribution of couplings, not in the regular square lattice and local degrees of freedom.
I am not sure if one can expect to find solutions for the ground state of such a spin glass in the first place.
OK, it's very interesting that arguments from the theory of computation, the halting problem and so on, can be used to show that there are no formulas for, say, the magentization of the ground state.
But I do not know what to conclude from this, given the fact that one is dealing with a very complex spin glass where one doesn't expect to find such formulas to begin with.
Cheers,
Stefan
hi bee!!! just visiting here to your wonderful blog! have a great day!
ReplyDeleteUnfortunately link has been outdated, yet the principal I would be considering in context of an information processing centre?
ReplyDeletePhysicists have succeeded in entangling five photons for the first time. Although four photons have been entangled before, five is the minimum number needed for universal error correction in quantum computation. Moreover, the same team has demonstrated a process called "open-destination teleportation" for the first time (Z Zhao et al. 2004 Nature 430 54). The results represent a major breakthrough in efforts to exploit the laws of quantum mechanics in quantum information processing.
By taking advantage of quantum phenomena such as entanglement, teleportation and superposition, a quantum computer could, in principle, outperform a classical computer in certain computational tasks. Entanglement allows particles to have a much closer relationship than is possible in classical physics. For example, two photons can be entangled such that if one is horizontally polarized, the other is always vertically polarized, and vice versa, no matter how far apart they are. In quantum teleportation, complete information about the quantum state of a particle is instantaneously transferred by the sender, who is usually called Alice, to a receiver called Bob. Quantum superposition, meanwhile, allows a particle to be in two or more quantum states at the same time
I mean sure, you could have a philosophical position but experimentally where is that philosophy taking you?:)
Spotting the quantum tracks of gravity waves by Zeeya Merali
Their calculations show that as the gravitational force from a passing wave slightly changes the momentum of the entangled particles, it should knock them out of their pristine spin state. In principle, that effect could be detected, but it is so small that no one has found a way to pick it up, explains Yeo. He and his team suggest that the effect could be amplified using a process called "entanglement swapping", which allows pairs of particles that have never been in contact to become entangled. "Spin and momentum become entangled to a higher degree so that changing one produces an even larger change in the other," says quantum physicist Chris Adami at the Jet Propulsion Laboratory in Pasadena, California.
I mean sure, what does it look like in terms of completion of the standard model to include, and then, you move consideration beyond gamma ray to consider what the universe actually looks like in regards to gravity waves?
ReplyDeleteAre they real?
You have to consider the energy valuation of the photon then to think hmmm..... what is this actually representing while one is being so presumptuous about the perspectives of Lagrangian views ad three body problems, as we look out to complete the views of our cosmos?
Get over it and get on with it.
Best,
Dear Arun,
ReplyDeleteYes, exactly that is the point. Best,
B.
Hi Phil,
ReplyDeleteThere is a subtle point in this example that I am not sure I made very clear. The state of the system considered is not evolving. It is a static two-dim representation that is analogous to the outcome of running a code. There is thus no sense in which one could think of this case as being a program 'running'. Best,
B.
Hi Anonymous,
ReplyDeleteThanks for the reference, I will give that a read! Best,
B.
Dear Stefan,
ReplyDeleteYes, I would agree the system they consider is far from being natural. I think this is more a proof 'in principle'. As to the groundstate, I think it is relevant that there is this one-dimensional line on which spins are forced into a specific orientation by an external field. This fixes the state of the whole system. Since each line determines the next by construction of these 'designer blocks' there is no ambiguity in the ground state. And there is also no large difficulty in computing it, line by line. The problem is just that even though you could do that, you can't derive any macroscopic variables that would describe properties of the state. Best,
B.
Hi Bee,
ReplyDelete“The development of macroscopic laws from first principles may involve more than, just systematic logic, and could require conjectures suggested, by experiments, simulations or insight.”
Actually after reading the paper of which the above forms to be the conclusion I understand it to more or less agree rather the disagree with Penrose’s position. That is it's contention as to what's required runs outside the limits of systemic logic, which in this case is computing. The experiments and simulation mentioned are rather standard fair within traditional science yet the insight to me would correlate with consciousness, which of course is Penrose’s point to begin with.
Best,
Phil
Hi Plato,
ReplyDelete“By taking advantage of quantum phenomena such as entanglement, teleportation and superposition, a quantum computer could, in principle, outperform a classical computer in certain computational tasks”
I find it somewhat amusing that we believe that only now we may become the first to be able to exploit the quantum for the purposes of problem solving when the plants of the world have been doing it for eons.
Best,
Phil
P.S. I wonder how the vegetarians will take it if it becomes to be understood that their source of sustenance also is self aware:-)
I've remember doing some work in the past on Hopfield artificial neural networks which are based on these Ising lattices. Basically a huge network of interconnected elements, with every element connected to every other element (which in this case is supposed to resemble the human brain). And when you run the simulation it all settles down to a energy minimum (simulated annealing), but there are several possible minima, so this then resembles a human memory, as the whole system settles down to one particular "memory". But you have no way of knowing which "memory" is going to be remembered until you run the simulation.
ReplyDeleteOf course, all this cellular automata stuff is famous for being a research dead-end. Nothing seems to have come of any of it (unless you believe Steven Wolfram).
I have not read the paper under discussion, but your summary is misleading: "without actually running them and looking, thus one can never say anything about the total evolution [...] this then means there are questions about its ground state that can't be answered either [...] There is thus no way to derive this quantity from the Hamiltonian, the question is undecidable."
ReplyDeleteThe fact that a relation is undecideable does not mean that we cannot answer interesting questions about it. Undecidability means there is no computable algorithm to make this decision on the whole class of relevant problems. Let's consider the halting problem, the prototypical undedidable relation. It says that the function H from the set of all programs to the set {0, 1} which returns H(P) = 1 exactly when P does terminate when run. This is not computable. However, we can still look at concrete programs and find out whenther they terminate or not. The program
x := 1; x := x+1; return x
for example will terminate, while
10 goto 10
will not, and it's easy to prove either statement in ZFC. In summary: Undecidability do a problem does not mean we cannot say anything interesting about instances of the problem.
Hi Anonymous, yes, you're right considering the Halting problem and saying that in general it is not possible to say that a computer program will continue forever: that is uncomputable, but individual instances might be calculated. So I think the Halting problem is very misleading in this case. A bit of explanation:
ReplyDeleteAccording to algorithmic information theory, you can't write a computer program to discover whether another program will halt if the complexity of the program you are examining is greater than the program you are writing to examine it: in that case, the question is undecidable. Of course, you could write a computer program to determine if a simple program would halt: then it would be decidable. So some halting problem examples you can decide, and some you can't. But in the general case it is undecidable.
However, undecidability means just that: you can't write a program or a mathematical proof to prove it. Undecidability means you can't decide it. Full stop.
Hi Anonymous,
ReplyDeleteSorry if my formulation was misleading. There are of course settings in which you can say something about the ground state from knowing the initial conditions and the update rule. The point is there are some in which you can't. Best,
B.
Phil:I find it somewhat amusing that we believe that only now we may become the first to be able to exploit the quantum for the purposes of problem solving when the plants of the world have been doing it for eons.
ReplyDeleteThere is no doubt on my part that neural point of consideration(tabla rusa) will have been dedicated to "welcher weg?"
So this is "beyond once assumed" and presented for consideration.
>The Single Photon Experiment at Rowan University is a Success!
Entanglement applies to two or more particles even if one of them is used as input to the two slit experiment, it is not applicable to single particle experiments.
Afshars experiment is conducted in such a manner that it is the setup of the experiment coupled with the conservation of momentum that allows us to know exactly which slit the photon has gone through.
Whilst knowing which way the photon has gone we also manage to show the absence of interference with both slits open via interference minim.Variation of the Standard Two-Pin-hole "welcher-Weg" Optics Experiment
While you have identified this in a "natural process" and one which I am quite fond of on many levels, it does go to the heart of what is allowed to intervene in that neurological gap, not only in the idea of consciousness including ingenuity, but in the experimental process as well.
U(1) is "part of a beginning" in the formation of our cosmos. Any successful perception would entail keeping part of the inclusion of attributes on one level, consistent with what is revealed on another?
Best,
I think my response to Anonymous yesterday about the Halting Problem was misleading. Whether or not a problem is undecidable (or uncomputable) depends on the axiomatic system you choose in mathematics. Excuse me for posting my corrected version as much to get things clearer in my own head as anything else (this is still kind-of on-topic):
ReplyDeleteWe're all probably aware of Godel's Incompleteness Theorem in mathematics which states that for a particular, specified Formal Axiomatic System (FAS) (i.e., a mathematical set of theorems built-up from fundamental axioms) then there will always be a theorem which is true but you cannot prove (from those particular axioms). That theorem is then said to be undecidable (for that particular FAS).
Likewise, Turing found a very similar result in computing. Let's imagine we have a computer program and we want to know if it will halt (i.e., return a result) or not (i.e., by getting stuck in an infinite loop). Now, just running the program will not give us an answer for all cases because even if the program does not halt after 1,000 years that does not prove that it will never halt - it might halt after 1,001 years. So there is is no way to tell if a program will never halt just by running it.
So, with this in mind that it is impossible to get a definite answer by running the program, let's try to find an answer by writing a second really intelligent program (let's call it a "termination tester") which will tell if the first program will halt or not merely by examining the code, by doing some sort of pattern recognition on the code, but not by running the program.
Now, Turing's Halting Problem result says that for that particular termination tester there will always exist a program which it is unable to tell whether it halts or not. Like I said in my earlier post, this will be the case if the algorithmic complexity of the program we are testing is greater than the algorithmic complexity of our termination tester program. Our termination tester will be simply not up to the job - the question is too hard for it.
So there is a very close connection between an FAS in maths (and Godel's Incompleteness Theorem) and a termination tester computer program (and Turing's Halting Problem). Given a specific FAS or termination tester there will always be a theorem which it cannot prove to be true or a program which it cannot tell if it halts or not.
If anyone wants to know more, I can recommend Gregory Chaitin's Meta Math book.
You write: "There are of course settings in which you can say something about the ground state from knowing the initial conditions and the update rule. The point is there are some in which you can't."
ReplyDeleteThis is still not quite right: there is no reason to believe that you cannot say anything about these states, all the paper (in your summary) shows is that you cannot mechanically derive what you want to say.
Sorry for being pedantic.
Andrew writes: Whether or not a problem is undecidable (or uncomputable) depends on the axiomatic system you choose in mathematics.
ReplyDeleteThis is correct, but the interesting question is not only the mathematisation of the intuitive notion of computation by Church, Goedel, Post, Zuse and others, but also the empirical content of what is now called the "Church-Turing" thesis. If it were to turn out that infinitely fast machines could be built, the notion of computability would change, and if we cannot build arbitrary Turing machines (as I belive we cannot in this universe), then the notion of computability is a proper overapproximation of what can be computed. Be that as it may, it's an empirical question.
Hi Anonymous,
ReplyDeleteThis is still not quite right: there is no reason to believe that you cannot say anything about these states, all the paper (in your summary) shows is that you cannot mechanically derive what you want to say.
Sorry for being pedantic.
Sorry for being dumb but I don't understand that. What do you mean with 'mechanically derive'? You can either derive it or you can't. If you like you can guess something alternatively, that I wouldn't call a derivation, but it's of little help. Best,
B.
Bee,
ReplyDeleteIt would be interesting to see whether one could find a possibly weaker statement for large, but finite systems.
Why don't you consider the statement you made about cellular automatons (which can be physically built in a variety of ways) to be this weaker statement?
Let P be the set of all programs. Consider the function H : P --> {0, 1} such that H(p) = 1 iff the execution of P terminates.
ReplyDeleteTuring proved in ZFC that there is no Turing machine computing H. This result is called "Undidability of the Halting problem". The Church-Turing thesis, at least in my reading, says that there is no physical device in the universe that computes H either. The CTT is a statement of physics.
It is crucial to note that the halting function H is defined on the set of all programs.
Hence it is not ruled out that for any given program P, I or you, or anyone, or a machine can prove (e.g. produce a proof in ZFC) that P halts or not.
For the same reason, I believe that the paper you summarise does not rule out that we gather information about specific spin systems. There just won't be an algorithm that derives the property automatically for all such systems.
Hi Anonymous,
ReplyDeleteI believe that the paper you summarise does not rule out that we gather information about specific spin systems
I don't think so either, and I never said that. Best,
B.
Prof. Hossenfelder -
ReplyDeleteIt would be interesting to see whether one could find a possibly weaker statement for large, but finite systems.
I haven't read the paper yet, but I'll go out on a limb and say 'no'. (I'm often out on a limb - that's why I keep falling out of trees!) The point that allows this model to be Turing-complete (a general computer) is that there are infinite degrees of freedom - the lattice has infinitely many spins. (This is analogous to the infinitely-long tape in the Turing machine, or the infinite RAM memory in the von Neumann computer; more relevantly, the infinite grid size in a cellular automaton). Such a computer can perform computations where it goes through infinitely many unique states without ever halting, and this allows it to possibly have uncomputable behavior (halting problem).
In contrast, where there are only finite degrees of freedom, the system as a whole can only enter finitely many states - so by enumerating them all, you can predict its behavior for all time (it must be cyclical - the time evolution depends only on the instantaneous state, not its history). In CS theory this is the difference between a "finite automaton" and a real Turing machine. Specifically: in this thought experiment, where there finite (though large) number of spins, you can construct the global Hamiltonian of the system from the component interactions by tensor products, and it is a finite matrix which you can diagonalize etc. You could not do that with an infinite-dimensional Hilbert operator. With a finite Hamiltonian, the usual observables are computable functions of the local interactions - reductionism works, at least by this metric.
-Thomas Szczarkowski
Hi Thomas,
ReplyDeleteI agree with you. That's why I said a similar statement, not the same. I don't doubt that reductionism works, the question is whether it is useful. Best,
B.