6 ms·

Classical sorting algorithms as a model of morphogenesis (2023)

166 points by filoeleven 2y ago

deleted 2y ago
[deleted]
ziofill 2y ago
I recommend Michael Levin’s YouTube channel. Lots and lots of fascinating discussions.
jstrieb 2y ago
The last coauthor listed on this preprint is Michael Levin, who has a lot of other cool work. In particular, this talk of his from NeurIPS 2018 includes fascinating biology research results, as well as musings on the future of biologically-inspired artificial intelligence. https://youtu.be/RjD1aLm4Thg https://youtu.be/RjD1aLm4Thg HN discussion about the talk: https://news.ycombinator.com/item?id=18736698 https://news.ycombinator.com/item?id=18736698
- jcims 2y ago
  He's on Lex Fridman's podcast as well - https://www.youtube.com/watch?v=p3lsYlod5OU https://www.youtube.com/watch?v=p3lsYlod5OU Great conversation.
- mycall 2y ago
  Artem Kirsanov has many great videos on this subject most of which I fail to absorb on first pass. https://www.youtube.com/@ArtemKirsanov/videos https://www.youtube.com/@ArtemKirsanov/videos
- filoeleven 2y ago
  I first found him through one of his presentations on YouTube. His other work is, to me, waaay more interesting and pertinent. His lab's model of what cancer is and their effective treatment of it using bioelectricity could very well be a game-changer. All the stuff about making two-headed flatworms using the same mechanics, with no changes to the genome, is fascinating. One of the companies he's with is working on a device to re-grow amputated limbs in humans. It's some serious sci-fi stuff. I chose to post this paper because text usually does better on HN than video, and it's an unexpected find in one of our basic tools. I fully expect his other research to show up here more often as it grows to fruition. Anyone interested in checking out more of his work can browse this list of his papers, which goes all the way back to 1995. https://drmichaellevin.org/publications/ https://drmichaellevin.org/publications/
  - throwaway314155 2y ago
    > Anyone interested in checking out more of his work can browse this list of his papers, which goes all the way back to 1995. https://drmichaellevin.org/publications/ https://drmichaellevin.org/publications/ Very delayed reply, but do you have any suggestions for which of his publications are most interesting so I can read those first?
mithametacs 2y ago
Building something that isn't Turing-complete is surprisingly-hard once it's complex enough. If basal intelligence is present in diverse computational structures, then weak intelligence is everywhere. If weak intelligence is everywhere, Earth-like planets are everywhere, ... where are the aliens? Personally, I blame game theory. Too many agents too smart in one place, you get conflicts, and eventually someone breaks an atom apart in your direction. Or do you need emotions to have conflict? Are there basal emotions? I'm usually not worried about AI uprisings, but I do believe in the possibility of conflict.
- fnord77 2y ago
  Where is it written that intelligent beings must create the means for interstellar communication, or any technology at all? Imagine a planet with highly intelligent whales who have no way to manipulate their environment (hands) and no need to.
  - Teever 2y ago
    Every organism manipulates their environment in some way. The ones that can manipulate it in a way that allows them access to more resources than the others will out compete the ones who don't.
    - abrookewood 2y ago
      Still hard to smelt metal if you live in the ocean.
      - bboygravity 2y ago
        That's why genetic mutations happened and they grew hands and started smelting on land. This happened.
    - gf000 2y ago
      Evolution doesn't really work like that. It's just a low bar that everything has to cross from time to time. Being a specialist, very advanced hunter is in no ways better than a dumb jellyfish that spawns billions of offsprings.
sitkack 2y ago
"The Collective Intelligence of Morphogenesis: a model system for basal cognition" by Michael Levin https://www.youtube.com/watch?v=JAQFO4g7UY8 https://www.youtube.com/watch?v=JAQFO4g7UY8 And from Machine Learning Street Talk Michael Levin - Why Intelligence Isn't Limited To Brains. https://www.youtube.com/watch?v=6w5xr8BYV8M https://www.youtube.com/watch?v=6w5xr8BYV8M
- sitkack 2y ago
  I highly recommend sitting down and really watching a couple talks by Michael Levin. After Robert Sapolsky, I haven't found a person that changed my perspective on whatever passes for reality more than Levin. https://drmichaellevin.org/ https://drmichaellevin.org/ (link to his lab) https://www.reddit.com/r/MichaelLevinBiology/comments/18x3vnq/hey_everyone_from_mike_levin/ https://www.reddit.com/r/MichaelLevinBiology/comments/18x3vn... Academic YT channel https://www.youtube.com/@drmichaellevin https://www.youtube.com/@drmichaellevin https://en.wikipedia.org/wiki/Robert_Sapolsky https://en.wikipedia.org/wiki/Robert_Sapolsky
InDubioProRubio 2y ago
A beach sorts itself by size of sand, just by applying physics, so any array copied by parallel processes will sort itself given enough time, by computation time spend on the element aka the size of the rocks.
- danwills 2y ago
  I think if you 'just apply physics' (let's say 'just apply computation' shall we?) then an array of numbers can only hope for this to happen In a kind of bogosort-style way?: Shuffle them all, and if now sorted, return! Else, loop and shuffle again, and so on. Such a hillarious sort algo.. but wait till u hear about bogobogosort! lollll! But different sizes of sand do move against each other differently, and I think maybe that aspect is slightly reminiscent of the every-cell-for-themselves aspect of the cells described in the paper, and especially how the different rules allow different swapping operations when the swap-target is smaller or larger than the current cell. So I think it's a very relevant observation!
  - InDubioProRubio 2y ago
    Its not.. parallelism in computation has physics, as in cycles spend per object. And you can totally sort something that way reliable. You can even "sieve" large objects out, by creating obstacles of size in that processed array. It even has a "lightspeed" aka computational object size in cycles * nr of parallel processors. So if you have empty parts of your array, you can insert elements at traveldistance there without violating causality
niemandhier 2y ago
This is fun, but I would call it an example of self organization / self organized complexity not intelligence. Cell membranes assemble themselves, so do micella ( little spherical protein baubles ), or to take a non living example lipid bilayers. We would not call such a system intelligent.
- danwills 2y ago
  One of Levin's main points is to describe agency/intelligence as a continuous spectrum rather than an on/off thing so within the framework of thought that this paper exists in, it's no longer meaningful to treat the answer to the 'is it intelligence?' question as having a boolean answer. I completely agree with this myself (and have for a long time before I even read any of Levin's frankly amazing work) and I think of the answer to this as more like a float/real-numbered thing - the amount of consciousness/intelligence/agency as a fraction of overall energy usage or something maybe? And that probably will lead to one constantly having to try to work out where the heck zero and one are all the time eh? heheh : ) I think it's fun and fascinating as well though for sure, and I think that even stuff as simple as a reaction-diffusion simulation, can actually contain some tiny elements of agency (just like this paper does with it's self-sorting cells!) Who cares what the scale is, right?, it's the same phenomena at the tiniest scales in my opinion, that led to life, that led to humans.
  - mjburgess 2y ago
    Whatever the purpose of this "sliding scale" is, it has little to do with the property of intelligence we are concerned with generally. When we say one species is more intelligent than another, one breed of dog, or one person -- we aren't describing a difference in their organisational structure. And when we want to build intelligent systems we aim to build things that have specific capacities, not that have this sort of abstract organisation which is entirely orthogonal to these capacities. One dog is more intelligent than another if it can read the intentions of its owner (theory of mind), coordinate in its environment (eg., open doors, etc.), plan more extended actions, pretend/fake actions to confuse the owner/other-dogs, and so on. These ranges of capacities do not follow from an abstract 'organisational' description of the dog. The great pseudoscience of this 'computer science' thinking is that abstracts to a degree of description that is almost universal, then claims to make fine-grained distinctions. That the earth-and-moon are 2, and the tree-and-bird are 2, does not mean the earth-and-sun and the tree-and-bird are sharing in any capacities at all. To instantiate an abstract description implies almost nothing.
danwills 2y ago
I just loved this bit in the paper, could be so easily taken on so many tangents!: ""Delayed Gratification is used to evaluate the ability of each algorithm undertake actions that temporarily increase Monotonicity Error in order to achieve gains later on. Delayed Gratification is defined as the improvement in Sortedness made by a temporarily error-increasing action."" Is it slightly analogous in some ways to the avoidance of getting stuck in local maxima perhaps?
- vindex10 2y ago
  Or maybe the fact that the path of minimal effort != sequence of paths with locally simplest steps.
  - danwills 2y ago
    I'd love to know more about what you mean! Is it that with a bit more upfront investment (or 'delayed gratification'), a system might be able to find shorter (or less energy-intensive) paths through the space that they are navigating to get to their targets? I think it certainly does seem like when there is essentially some 'computational slack' ('extra line' say, slightly over-provisioned or just set-to-explore more) I'd guess there's a good chance that that could yield a better (cheaper/shorter) result than a brute-force (minimal-effort, perhaps more technically 'efficient') solution? Unfortunately I don't really feel like I really went anywhere with what I said, but your very short comment made me wonder many things about what you meant! Appreciated!
danwills 2y ago
I loved this paper, below is the punchline for me I reckon (and summarizes where-they-are-at nicely too I think - finding out a lot of possibly very important things!): ""The discovery of unexpected problem-solving competencies (such as Delayed Gratification and segregation) that are not apparent from the component policies and algorithms themselves is a critical research program.""
trenchgun 2y ago
Are these just traditional distributed algorithms?

166 points by filoeleven 2y ago

deleted 2y ago

[deleted]

ziofill 2y ago

I recommend Michael Levin’s YouTube channel. Lots and lots of fascinating discussions.

jstrieb 2y ago

The last coauthor listed on this preprint is Michael Levin, who has a lot of other cool work. In particular, this talk of his from NeurIPS 2018 includes fascinating biology research results, as well as musings on the future of biologically-inspired artificial intelligence. https://youtu.be/RjD1aLm4Thg https://youtu.be/RjD1aLm4Thg HN discussion about the talk: https://news.ycombinator.com/item?id=18736698 https://news.ycombinator.com/item?id=18736698

jcims 2y ago
He's on Lex Fridman's podcast as well - https://www.youtube.com/watch?v=p3lsYlod5OU https://www.youtube.com/watch?v=p3lsYlod5OU Great conversation.
mycall 2y ago
Artem Kirsanov has many great videos on this subject most of which I fail to absorb on first pass. https://www.youtube.com/@ArtemKirsanov/videos https://www.youtube.com/@ArtemKirsanov/videos
filoeleven 2y ago
I first found him through one of his presentations on YouTube. His other work is, to me, waaay more interesting and pertinent. His lab's model of what cancer is and their effective treatment of it using bioelectricity could very well be a game-changer. All the stuff about making two-headed flatworms using the same mechanics, with no changes to the genome, is fascinating. One of the companies he's with is working on a device to re-grow amputated limbs in humans. It's some serious sci-fi stuff. I chose to post this paper because text usually does better on HN than video, and it's an unexpected find in one of our basic tools. I fully expect his other research to show up here more often as it grows to fruition. Anyone interested in checking out more of his work can browse this list of his papers, which goes all the way back to 1995. https://drmichaellevin.org/publications/ https://drmichaellevin.org/publications/
- throwaway314155 2y ago
  > Anyone interested in checking out more of his work can browse this list of his papers, which goes all the way back to 1995. https://drmichaellevin.org/publications/ https://drmichaellevin.org/publications/ Very delayed reply, but do you have any suggestions for which of his publications are most interesting so I can read those first?

mithametacs 2y ago

Building something that isn't Turing-complete is surprisingly-hard once it's complex enough. If basal intelligence is present in diverse computational structures, then weak intelligence is everywhere. If weak intelligence is everywhere, Earth-like planets are everywhere, ... where are the aliens? Personally, I blame game theory. Too many agents too smart in one place, you get conflicts, and eventually someone breaks an atom apart in your direction. Or do you need emotions to have conflict? Are there basal emotions? I'm usually not worried about AI uprisings, but I do believe in the possibility of conflict.

fnord77 2y ago
Where is it written that intelligent beings must create the means for interstellar communication, or any technology at all? Imagine a planet with highly intelligent whales who have no way to manipulate their environment (hands) and no need to.
- Teever 2y ago
  Every organism manipulates their environment in some way. The ones that can manipulate it in a way that allows them access to more resources than the others will out compete the ones who don't.
  - abrookewood 2y ago
    Still hard to smelt metal if you live in the ocean.
    - bboygravity 2y ago
      That's why genetic mutations happened and they grew hands and started smelting on land. This happened.
  - gf000 2y ago
    Evolution doesn't really work like that. It's just a low bar that everything has to cross from time to time. Being a specialist, very advanced hunter is in no ways better than a dumb jellyfish that spawns billions of offsprings.

sitkack 2y ago

"The Collective Intelligence of Morphogenesis: a model system for basal cognition" by Michael Levin https://www.youtube.com/watch?v=JAQFO4g7UY8 https://www.youtube.com/watch?v=JAQFO4g7UY8 And from Machine Learning Street Talk Michael Levin - Why Intelligence Isn't Limited To Brains. https://www.youtube.com/watch?v=6w5xr8BYV8M https://www.youtube.com/watch?v=6w5xr8BYV8M

sitkack 2y ago
I highly recommend sitting down and really watching a couple talks by Michael Levin. After Robert Sapolsky, I haven't found a person that changed my perspective on whatever passes for reality more than Levin. https://drmichaellevin.org/ https://drmichaellevin.org/ (link to his lab) https://www.reddit.com/r/MichaelLevinBiology/comments/18x3vnq/hey_everyone_from_mike_levin/ https://www.reddit.com/r/MichaelLevinBiology/comments/18x3vn... Academic YT channel https://www.youtube.com/@drmichaellevin https://www.youtube.com/@drmichaellevin https://en.wikipedia.org/wiki/Robert_Sapolsky https://en.wikipedia.org/wiki/Robert_Sapolsky

InDubioProRubio 2y ago

A beach sorts itself by size of sand, just by applying physics, so any array copied by parallel processes will sort itself given enough time, by computation time spend on the element aka the size of the rocks.

danwills 2y ago
I think if you 'just apply physics' (let's say 'just apply computation' shall we?) then an array of numbers can only hope for this to happen In a kind of bogosort-style way?: Shuffle them all, and if now sorted, return! Else, loop and shuffle again, and so on. Such a hillarious sort algo.. but wait till u hear about bogobogosort! lollll! But different sizes of sand do move against each other differently, and I think maybe that aspect is slightly reminiscent of the every-cell-for-themselves aspect of the cells described in the paper, and especially how the different rules allow different swapping operations when the swap-target is smaller or larger than the current cell. So I think it's a very relevant observation!
- InDubioProRubio 2y ago
  Its not.. parallelism in computation has physics, as in cycles spend per object. And you can totally sort something that way reliable. You can even "sieve" large objects out, by creating obstacles of size in that processed array. It even has a "lightspeed" aka computational object size in cycles * nr of parallel processors. So if you have empty parts of your array, you can insert elements at traveldistance there without violating causality

niemandhier 2y ago

This is fun, but I would call it an example of self organization / self organized complexity not intelligence. Cell membranes assemble themselves, so do micella ( little spherical protein baubles ), or to take a non living example lipid bilayers. We would not call such a system intelligent.

danwills 2y ago
One of Levin's main points is to describe agency/intelligence as a continuous spectrum rather than an on/off thing so within the framework of thought that this paper exists in, it's no longer meaningful to treat the answer to the 'is it intelligence?' question as having a boolean answer. I completely agree with this myself (and have for a long time before I even read any of Levin's frankly amazing work) and I think of the answer to this as more like a float/real-numbered thing - the amount of consciousness/intelligence/agency as a fraction of overall energy usage or something maybe? And that probably will lead to one constantly having to try to work out where the heck zero and one are all the time eh? heheh : ) I think it's fun and fascinating as well though for sure, and I think that even stuff as simple as a reaction-diffusion simulation, can actually contain some tiny elements of agency (just like this paper does with it's self-sorting cells!) Who cares what the scale is, right?, it's the same phenomena at the tiniest scales in my opinion, that led to life, that led to humans.
- mjburgess 2y ago
  Whatever the purpose of this "sliding scale" is, it has little to do with the property of intelligence we are concerned with generally. When we say one species is more intelligent than another, one breed of dog, or one person -- we aren't describing a difference in their organisational structure. And when we want to build intelligent systems we aim to build things that have specific capacities, not that have this sort of abstract organisation which is entirely orthogonal to these capacities. One dog is more intelligent than another if it can read the intentions of its owner (theory of mind), coordinate in its environment (eg., open doors, etc.), plan more extended actions, pretend/fake actions to confuse the owner/other-dogs, and so on. These ranges of capacities do not follow from an abstract 'organisational' description of the dog. The great pseudoscience of this 'computer science' thinking is that abstracts to a degree of description that is almost universal, then claims to make fine-grained distinctions. That the earth-and-moon are 2, and the tree-and-bird are 2, does not mean the earth-and-sun and the tree-and-bird are sharing in any capacities at all. To instantiate an abstract description implies almost nothing.

danwills 2y ago

I just loved this bit in the paper, could be so easily taken on so many tangents!: ""Delayed Gratification is used to evaluate the ability of each algorithm undertake actions that temporarily increase Monotonicity Error in order to achieve gains later on. Delayed Gratification is defined as the improvement in Sortedness made by a temporarily error-increasing action."" Is it slightly analogous in some ways to the avoidance of getting stuck in local maxima perhaps?

vindex10 2y ago
Or maybe the fact that the path of minimal effort != sequence of paths with locally simplest steps.
- danwills 2y ago
  I'd love to know more about what you mean! Is it that with a bit more upfront investment (or 'delayed gratification'), a system might be able to find shorter (or less energy-intensive) paths through the space that they are navigating to get to their targets? I think it certainly does seem like when there is essentially some 'computational slack' ('extra line' say, slightly over-provisioned or just set-to-explore more) I'd guess there's a good chance that that could yield a better (cheaper/shorter) result than a brute-force (minimal-effort, perhaps more technically 'efficient') solution? Unfortunately I don't really feel like I really went anywhere with what I said, but your very short comment made me wonder many things about what you meant! Appreciated!

danwills 2y ago

I loved this paper, below is the punchline for me I reckon (and summarizes where-they-are-at nicely too I think - finding out a lot of possibly very important things!): ""The discovery of unexpected problem-solving competencies (such as Delayed Gratification and segregation) that are not apparent from the component policies and algorithms themselves is a critical research program.""

trenchgun 2y ago

Are these just traditional distributed algorithms?