The new math of how large-scale order emerges
187 points
4 days ago
| 8 comments
| quantamagazine.org
| HN
jsenn
4 days ago
[-]
Very cool to see an article that discusses Crutchfield's Epsilon machine formalism. It's one of those rare theories that is conceptually powerful but also simple and concrete enough that it can be implemented in a couple hundred lines of code.

For those interested, [1] is a readable (if quirky) introduction to the theory. The paper discussed in this article seems to discuss a way of "stacking" epsilon machines, so that you have a machine that describes the state transitions of a machine that describes a data set. I wonder if this gets around the main weakness of the e-machine formalism, namely that for a process with non-finite memory, there's no obvious next class of automata to try after finite state machines. In a sense FSMs are the only non-arbitrary model of computation; everything else basically boils down to augmenting a finite-state control with a gadget for storing data, like a stack (pushdown automata), register (counter/register machines), random-access tape (Turing machines), random-access tape but you're only allowed a tape the size of the input (linear-bounded automata) etc. You can constrain that gadget in pretty much arbitrary ways, which makes it difficult to choose a computational model for a non-finite process.

[1]: https://csc.ucdavis.edu/~cmg/papers/CalcEmerg.pdf

reply
ganzuul
3 days ago
[-]
https://en.wikipedia.org/wiki/Model_of_computation

FSMs are sequential models and then there are functional models and concurrent models.

reply
habitue
4 days ago
[-]
This is really cool. Thanks for the link.
reply
gnulinux
4 days ago
[-]
Amazing paper, thank you for sharing!
reply
rramadass
4 days ago
[-]
What are some good resources (books/papers/videos/etc.) to get started on "Complex Systems", "Emergence", "Self-Organization" and related topics?
reply
dlojudice
4 days ago
[-]
"Introduction to Complexity" by Melanie Mitchell from Santa Fe Institute.

https://www.complexityexplorer.org/courses/185-introduction-...

This free course is based on her book "Complexity: A Guided Tour"

https://www.amazon.com/Complexity-Guided-Tour-Melanie-Mitche...

reply
rramadass
3 days ago
[-]
Thanks. I was aware of her book but not the course.
reply
chermi
4 days ago
[-]
Crutchfield has recorded lectures on YouTube. I thought they were quite good. I'm biased toward learning statistical mechanics and nonlinear dynamics as a starting point. Search "phy 256 a(b) crutchfield" on YouTube. Crutchfield has been doing amazing work for quite some time. If you want a critical and very entertaining read, I would check out cosma shalizi's blog. He does a lot of book reviews too that may be helpful. http://bactra.org/weblog/

Other names/references include "The nature of computation" Stuart kauffman. "Nonlinear dynamics and chaos"

Too many stat mech books to possibly recommend, for the idea of emergence you'll want something including phase transitions so... Can't go wrong with 'thermodynamics and an introduction to thermostatistics". And for stat mech with lots of complex systems diversions, Sethna's book is excellent but difficult to learn from. "Entropy, complexity, and order parameters. Names in thermo/complexity: Sethna Goldenfeld Parisi HE stanley

Finally, it's hard to talk about complex systems without talking about networks, "Networks"-Newman is unambiguously the best choice. Names in networks: Mark Newman Reka Albert Avoid barabasi especially more recent stuff.

There may be better lectures/resources out there I don't know of, but I would start with crutchields lectures. Note again I am coming from heavy physics bias.

reply
rramadass
3 days ago
[-]
Thanks! There is a lot here to study/research on; appreciate your writing it out.
reply
abetusk
4 days ago
[-]
Complexity and Criticality by Christensen and Moloney [0]. It goes through three main systems, percolation, the Ising model and the rice pile model. It's an introduction that gives the tools to analyze each and provides the foundation to understand other models and other literature in the area.

I found it pretty accessible from a programmers point of view.

[0] https://www.amazon.com/COMPLEXITY-CRITICALITY-Imperial-Colle...

reply
rramadass
3 days ago
[-]
Thank you; This looks pretty interesting.
reply
JPC21
4 days ago
[-]
Personally I would read a book on statistical physics instead, since this is where the study of 'emergence' began. The Feynman lectures would be good for this.

I actually haven't found many good books for 'Complex systems', but if you want to take a shot anyway, I would look at https://academic.oup.com/book/25504 and https://press.princeton.edu/books/paperback/9780691122045/cr...

reply
rramadass
4 days ago
[-]
Great. The OUP book linked above viz. Introduction to the Theory of Complex Systems by Stefan Thurner et al. looks particularly good since the ToC lists all the needed interdisciplinary topics for a study of this subject.
reply
uoaei
4 days ago
[-]
Prerequisites are heavily aligned with physics / applied math, particularly: thermodynamics, dynamical systems, network theory, and a strong emphasis on interdisciplinary study. All should be approached from a perspective rooted mostly in rigorous information theory.
reply
rramadass
4 days ago
[-]
Well said. This recommendation from user JPC21 seems to cover everything you list - https://news.ycombinator.com/item?id=40644189
reply
uoaei
4 days ago
[-]
I did a master's in complexity science and a lot of it was basically "what if this graph of things is a computer? what does it compute?"
reply
rramadass
3 days ago
[-]
What were the textbooks used in your master's course?
reply
FergusArgyll
4 days ago
[-]
Kind of tangentially related but I think pretty relevant is Scale by Geoffreys West
reply
rramadass
3 days ago
[-]
Thanks; this is definitely related and relevant. The 3rd chapter of this book is on Scaling - https://news.ycombinator.com/item?id=40644189
reply
pdfernhout
4 days ago
[-]
My wife (Cynthia F. Kurtz) wrote a non-mathematical book on complexity a couple years ago: "Confluence: Tools for Thinking about How Organized Plans and Self-organized Patterns Flow Together" https://www.cfkurtz.com/confluence/

The blurb: "A path winds its way through a forest. Why does it go the way it goes? Did someone design it? Or was the path made smooth by feet that chose the smoothest path? Maybe some of both? Confluence examines the many ways in which organized, intentional plans (like paths we design) and self-organized, unintentional patterns (like paths that emerge where we walk) intermingle (happen at the same time and place) and interact (influence each other). The book lays out seven “thinking spaces” (like this one) that explore various aspects of the structures and relationships that flow together in our lives."

reply
rramadass
3 days ago
[-]
Thank you; looks quite interesting and different from the rest.
reply
epsilonic
4 days ago
[-]
Anything by John H. Holland is good.
reply
rramadass
4 days ago
[-]
Thanks. I have his Hidden Order book and also Per Bak's How Nature Works. Any others you would recommend by these or other authors?
reply
danyala
4 days ago
[-]
I can't recommend books but here are a couple of other good phrases to search with, or just to discuss with one of the sparkier LLMs, which tend to find this topic quite interesting:

1. cross-scale interaction

2. downward causation

Would be happy to learn of other terms too.

reply
rramadass
4 days ago
[-]
I generally find Wikipedia a very good starting point to get an overview and a gateway to further research/study; their "See Also" sections list plenty of terms/phrases to look up;

1) https://en.wikipedia.org/wiki/Complex_system#See_also

2) https://en.wikipedia.org/wiki/Self-organization#See_also

3) https://en.wikipedia.org/wiki/Emergence#See_also

reply
fiforpg
4 days ago
[-]
This Quanta trickled through my head

Like water through a sieve.

reply
nico
4 days ago
[-]
> exemplifying the way large-scale patterns and organization can arise from innumerable microscopic interactions

Is it proven that the flow of emergence is from micro to macro?

ie. Can emergence go the other way? What’s the starting point of the process? Can a macro process cause micro processes? Or is it always the other way around? Does causality always run in one direction?

reply
naasking
4 days ago
[-]
What would be an example of a macro process causing a micro without going through micro processes?

I would think the best you can do is something like fractal geometry, where self-similarity appears at all scales. In some sense, the rules are both micro and macroscopic. An example where this might have real-world implications is Palmer's Invariant Set Theory, which suggests that this fractal structure shapes both cosmological structures and what we see in quantum theory, eg. like violations of Bell's inequality,

reply
benfarahmand
4 days ago
[-]
I can't think of physical processes that could go from macro -> micro. The examples I can think of stem from Yuval Harari's human fictions affecting the world. For example, a nation state or a corporation or a story could set the stage for the macro affecting the micro. If we look at a story, it communicates an idea that changes the behaviors of humans, which in turn causes those humans to interact with the micro and the macro.

As I'm writing this out and thinking about it, where would fictional objects fit on the micro <--> macro axis?

reply
naasking
4 days ago
[-]
Fictions are encoded in the brain's microstates and drive its behaviour, comparable to how gate charge on transistors drives a computer state. But that is an interesting thought, because all of those microstates and their evolution are counterfactually described by a computer program, and much like math, perhaps a computer program in some sense has a platonic existence that isn't reducible to physical states. I probably wouldn't go in that direction, but some philosophers have made this case for math.
reply
boxfire
4 days ago
[-]
The Mars global dust storm is caused by coupling of angular momentum of the (solar) system, a global a effect. The Mars system itself down to the dust does not create sufficient conditions
reply
naasking
4 days ago
[-]
That coupling is due to aggregate interactions of all system particles, so it's still comes down to a cumulative microscopic effect. Pretty good example though!
reply
boxfire
3 days ago
[-]
I think one of the reasons I have that example is that specific dynamic is cited in most planetary science texts as "de-coupled", "invariant", etc etc, when in fact it's the major casual influence here, which was quite a surprise in recent years [glances at climate mostly still beating to the tune that particle inertia does not have to care about the system angular momentum variance at the solar system scale]
reply
Erem
4 days ago
[-]
Would lunar gravity -> tides -> waves -> erosion of particles from a rock count?
reply
tines
4 days ago
[-]
"Lunar gravity" is the effect of innumerable individual particles exerting a gravitational force, so that's not really macro.
reply
GoblinSlayer
4 days ago
[-]
Maxwell demon?
reply
Blahah
4 days ago
[-]
Medicine
reply
naasking
4 days ago
[-]
Medicine is all biochemistry.
reply
ganzuul
3 days ago
[-]
Placebo is also medicine.
reply
naasking
3 days ago
[-]
Placebo is largely regression to the mean, so it's more like statistics.
reply
hammock
4 days ago
[-]
How about high pressure creating diamonds? Wars creating great (not in the normative sense) leaders? Climate and natural disasters creating selection pressure?
reply
hallgrim
4 days ago
[-]
Not sure but turbulent diffusion might be an example? Fluid dynamics is emergent from its constituent particles, creating sometimes vortices etc. which can decay into ever smaller vortices through the fluid’s coarser dynamics. At some point the vortices become so small that the kinetic energy is turned into diffusive behavior at the particle level instead.
reply
PaulDavisThe1st
4 days ago
[-]
Doug Hofstadter's concept of "heterarchy" is somewhat apropros here. A heterarchy matches TFA's concept of a "closure" (information about the micro doesn't really aid in predicting or understanding the macro), but adds in the ability for higher (more macro) levels to feedback to the lower (more micro) levels.

I don't know how much Hofstadter still invests in this idea, but at the time of GEB, he seemed pretty convinced it is/was a central part of how complex systems like minds/brains function.

reply
wslh
4 days ago
[-]
I started reading the abstract and thought immediately about Gregory Chaitin [1] measure of complexity, then searching on the text it is obviously there. I think it is a simple and good read to review Solomonoff–Kolmogorov–Chaitin [2] before reading the paper.

[1] https://en.wikipedia.org/wiki/Gregory_Chaitin

[2] https://en.wikipedia.org/wiki/Kolmogorov_complexity

reply
badrunaway
4 days ago
[-]
Can someone summarise what this changes overall in the field? What I got is that there was no proper formalism to study emergence earlier and now we have a mathematical framework.
reply
danyala
4 days ago
[-]
I wish Descartes and his peers could have lived to see this. It must have been misery.
reply
peter_d_sherman
4 days ago
[-]
>"A complex system exhibits emergence, according to the new framework, by organizing itself into a hierarchy of levels that each operate independently of the details of the lower levels.

The researchers suggest we think about emergence as a kind of “software in the natural world.” Just as the software of your laptop runs without having to keep track of all the microscale information about the electrons in the computer circuitry, so emergent phenomena are governed by macroscale rules that seem self-contained, without heed to what the component parts are doing.

Using a mathematical formalism called computational mechanics, the researchers identified criteria for determining which systems have this kind of hierarchical structure."

[...]

>"Indeed, the degrees of freedom, or independent variables, that capture the behavior of these systems at microscopic and macroscopic scales have precisely the relationship that the theory predicts."

Related:

https://en.wikipedia.org/wiki/Hierarchy

https://en.wikipedia.org/wiki/Dimension

https://en.wikipedia.org/wiki/Degrees_of_freedom

https://en.wikipedia.org/wiki/Phase_space

https://en.wikipedia.org/wiki/Computational_mechanics

https://en.wikipedia.org/wiki/Partial_differential_equation

https://en.wikipedia.org/wiki/Self-organization (a.k.a. "Self Organizing System(s)")

https://en.wikipedia.org/wiki/Consciousness

https://news.ycombinator.com/item?id=39860388

https://en.wikipedia.org/wiki/Emergence

And they're all related!

Magic!

reply