Mathematical Simplicity May Drive Evolution's Speed
quantamagazine.org
quantamagazine.org
It reminds me of demoscene, specifically "A mind is born"[1], 256-byte demo which "looks" complicated and with rich structure, but it's just nudged/selected random data. Author said that he played around with some random generated content until he found something nice. Just by itself that 256 bytes is still not enough to replicate behaviour, it must be run on hardware, which is like "environment" for DNA. Without several supporting chips which are easy to access, that code would mean nothing and would not generate such complexity. Moreover, those "patterns" in demo are patterns only because WE interpret them as meaningful.
I really, really enjoyed the course. It was very interactive and Hector was involved actively on forums with the students. Post the course, Hector suggested a couple of research directions and groups of students (myself included) are following different research directions. Here’s the Google Group https://groups.google.com/forum/m/#!forum/algodyn (we have a slack group too).
I’m myself part of a group where we are trying to create a crypto-currency approach of exploring Turing Machines and their outputs. In case, anyone’s interested let me know. (Hope if that proof of work wastes computation. What if we could instead do useful work of computing universal distribution of algorithmically generated strings). In case anyone is interested in contributing to the project, our project meeting notes and goals can be accessed in this doc https://docs.google.com/document/d/1np8cuFgfdrtRIaPL3oJPmmf_...
Overall, I’m very excited that researchers like Hector are making the field of algorithmic information theory more popular.
A lot of papers showing progress on computable approximations have been published just within the last year. There was one recently showing that the halting problem is in fact solvable for “almost all” Turing machines, which is a bit surprising; I would have not thought this was the case. Ultimately though, we don’t need to find the absolute shortest Turing machine that produces a given output string — we just need to find a decently short one that performs better than our existing models. Any sort of algorithmic approach is bound to be vastly superior to a purely statistical approach.
Also, is your code for exploring Turing machines public? We could perhaps use it in our project (see my other comment)
My code isn't public at the moment. It's written in Julia and rather messy so I'd have to clean it up a bit, but I wouldn't be opposed to putting it on Github.
I really like your project idea btw. It never occurred to me that all that time and energy wasted on proofs of work could be spent approximating the universal distribution. That could be really valuable.
Most of the problems with sharing messy code are purely in the author's head ("please don't let other people know how terrible my code is") and once you actually bite the bullet and just push the code, it turns out to be like most secrets, really stressful to keep secret and actually not that big of a deal once everyone hears it.
And for the real code problems, the broken corner cases and unfinished tests, well, if you put it on Github someone else might fix it for you :-)
Is this in the same sense as "almost all numbers are not natural numbers", and if yes, then what good does this bring?
The real challenge would be to show that "interesting" programs (i.e. that generate some sort of real world data) are solvable. There have been similar efforts in the field of complexity theory that aim to show certain NP-hard problems are tractable in the case of real world data (as opposed to a pathologically selected worst-case problem).
> approximate the algorithmic information content of a network
Haven't read the paper, but I'm not seeing how you could approximate it without throwing the baby out with the bathwater.
> bias evolving programs toward simplicity [...] Rewarding something like shorter program lengths, for example
Seems the simplest way to incorporate simplicity.
However, e.g. some simple organisms have far longer DNA than us. And as for larger building blocks, e.g. cells, slime molds are unicellular with many features of higher life.
The structure observed in nature is a byproduct of structures being a larger unit to navigate search space: like taking a highway, then main road, then side street to reach your destination. Or to home in on a decimal integer by varying any individual digit, instead of only adding +1 or -1 to the entire number.
The search strategy modifies the probability density over the search space, rather than restricting it (or, explicity modifying the fitness function over the search space), yielding emergent structure.
Much like “weeds”, when referring to plants, is a distinction that is only relevant in the context of human agriculture, so it is for “invasive species”. All life is, by definition (reproduction), invasive.
But, like I said, no expertise, just my initial reaction to your comment.
Like I feel like there is an inherent observer bias in the way survival is being defined, it feels more like "observable." Like in the local time of a tree snapshot (from its perspective), time may feel different than from ours observing it.
Are you sure about that? Viruses too? (depends on your definition of "living" of course) To clarify: I don't know if there is or isn't, I just don't think anyone does.
BTW this organism is called LUCA. Read: https://en.wikipedia.org/wiki/Last_universal_common_ancestor
No, there isn't. There's an ancestor population.
"This organism survived objectively better than any other organism of its time"
No, it did not survive. Being an ancestor is not survival. And this has nothing to do with "optimization" ... if evolution optimizes survival, then your "single common ancestor" predated optimization. You're just throwing concepts together to support a prior belief, but the facts don't work that way.
"I think it's possible to define survivability objectively using a little graph theory."
Maybe you should actually try it. Perhaps then you would notice that your notion of "optimized survivability" is about the future, but you're talking about graphs of the past.
It allowed those components that were useful to be duplicated, redone, and rearranged to form higher-order tools. Where the components remained relatively stable, but were remixed, redone, reordered, and otherwise reused - with only slight modification to lock them into their new tool.
We see this with the results of evolutionary modifications to DNA. One of the proteins responsible for multi-cellularity is itself a mashup of 4 or 5 proteins found in single-celled organisms, but where those smaller proteins are repeated, smashed together, and otherwise remixed to form a protein with a new function that was synergistic with the original components. And that synergy allowed for the higher-order complexity associated with multi-cellularity [1]. And once that took off and proteins started to get large, the proteins would themselves be split up into pathways - and then those pathways would get duplicated. Etc. And this is just one mechanism real life has used evolution to scan that underlying space more rapidly than random walks.
This is actually what we do at Serotiny [2] - we don't design novel proteins by sequence (in the 20^300 landscape) but rather by functional domain (in the 20000^5 landscape). And I think there are mechanisms to incorporate that kind of scaling layer into a good genetic algorithm that allow you to traverse short paths by going upwards into the different space, and then coming back down when you need granularity,
And so, I think when going back to the algorithms, if you want to make them pragmatic rather than theoretical, many scales should be addressed simultaneously.
> “DNA is extremely important, but it makes no sense if [it is] not in a cell, in an organism, in an ecosystem.” Other interactions are at play, and this application of algorithmic information cannot capture the extent of that complexity.
Yep.
"DNA is extremely important, but it makes no sense if [it is] not in a cell, in an organism, in an ecosystem. Other interactions are at play, and this application of algorithmic information cannot capture the extent of that complexity."
Completely mischaracterizes the research (Zenil et al.). They are looking at networks evolving over time of interacting elements. Such elements are genes but networks can also be metabolic or signaling and everything they say still holds.
The subsection about chasing dynamic evolving targets even addresses the question of ever-changing environments that have some raised here. So the approach is way beyond treating life as 'DNA' but even so, I doubt anyone would object about the power of CRISPR-CAS9 only because it targets DNA... DNA is still the most fundamental element of life and other tend to embrace mysticism and are quite cartoonish about life.
Anyway, my recommendation is, do read the paper.
> Our embedded computational network architecture can be interpreted either at the levels of cells (internal network of molecules such as genes, proteins, metabolites) or alternatively as group or module of cells effective performing input-output transformation of external signals relative to the module. Naturally, this does not exclude a nested architecture ranging from cells encapsulating molecular networks to interacting modules composed of cells
And in fact the study actually meshes quite nicely with the paper cited before showing the evolution of signaling networks in multi-cellular systems.
https://www.youtube.com/watch?v=RlYS_GiAnK8
> Few people remember Turing's work on pattern formation in biology (morphogenesis), but Turing's famous 1936 paper On Computable Numbers exerted an immense influence on the birth of molecular biology indirectly, through the work of John von Neumann on self-reproducing automata, which influenced Sydney Brenner who in turn influenced Francis Crick, the Crick of Watson and Crick, the discoverers of the molecular structure of DNA. Furthermore, von Neumann's application of Turing's ideas to biology is beautifully supported by recent work on evo-devo (evolutionary developmental biology). The crucial idea: DNA is multi-billion year old software, but we could not recognize it as such before Turing's 1936 paper, which according to von Neumann creates the idea of computer hardware and software.
- - - -
Also "Algorithmically probable mutations reproduce aspects of evolution such as convergence rate, genetic memory, and modularity"
https://arxiv.org/abs/1709.00268v8
> Natural selection explains how life has evolved over millions of years from more primitive forms. The speed at which this happens, however, has sometimes defied formal explanations when based on random (uniformly distributed) mutations. Here we investigate the application of a simplicity bias based on a natural but algorithmic distribution of mutations (no recombination) in various examples, particularly binary matrices in order to compare evolutionary convergence rates. Results both on synthetic and on small biological examples indicate an accelerated rate when mutations are not statistical uniform but \textit{algorithmic uniform}. We show that algorithmic distributions can evolve modularity and genetic memory by preservation of structures when they first occur sometimes leading to an accelerated production of diversity but also population extinctions, possibly explaining naturally occurring phenomena such as diversity explosions (e.g. the Cambrian) and massive extinctions (e.g. the End Triassic) whose causes are currently a cause for debate. The natural approach introduced here appears to be a better approximation to biological evolution than models based exclusively upon random uniform mutations, and it also approaches a formal version of open-ended evolution based on previous formal results. These results validate some suggestions in the direction that computation may be an equally important driver of evolution. We also show that inducing the method on problems of optimization, such as genetic algorithms, has the potential to accelerate convergence of artificial evolutionary algorithms.