6 ms·

Computational Life: How self-replicating programs emerge from simple interaction

• p1esk 2y ago
  They use Brainfuck language for the experiments. Seriously.
  • Zondartul 2y ago
    It's convienient because any random collection letters is a "valid" brainfuck program.
    • optimalsolver 2y ago
      StupidStackLanguage also has this pleasing property: https://esolangs.org/wiki/StupidStackLanguage https://esolangs.org/wiki/StupidStackLanguage
      • metadat 2y ago
        Wow, some of those programs are actually interesting, I want to try cat (implemented as simply "jf"), and some of the other ones further down the list. I almost can't believe this is my first time encountering StupidStackLanguage.
      • 29athrowaway 2y ago
        The high amount of operators makes it harder to mutate the program iteratively into something that does what you want.
      • stephen_cagle 2y ago
        Is every program valid? What if the "end loop" occurs before the "begin loop"?
    • dekhn 2y ago
      Interesting! That's analogous to some recent work in chemistry. Historically, there was a string representation for molecules called SMILES, which is fairly terse and, when canonicalized, maps from strings to individual molecules (2D topology). However, not all strings are valid SMILES. Recent work with autoencoders to turn SMILES strings into a vector representation via embedding creates models that often generate invalid SMILES strings (the popular paper about this glosses over this fact). For example, if your training set includes both bromine (represented as Br) and chlorine (represented as Cl) and you generate random vectors, they might decode to contain Bl, which is an as-yet unmade element. This is not desirable (although opinions vary). As a result, the group that published the earlier work developed a new compact representation known as SELFIES (https://github.com/aspuru-guzik-group/selfies https://github.com/aspuru-guzik-group/selfies) where it's effectively impossible to generate invalid decodings of strings (every SELFIE string decodes to a valid molecule). I'm not sure what the terminology for these sorts of features of encodings.
      • blackbear_ 2y ago
        At the risk of bringing this analogy too far, there was a recent paper [1] arguing that the ability to generate invalid SMILES is beneficial and allows the model to more accurately represent the target distribution compared to SELFIES. This could be similar to mutations allow one to explore a wider range of options, although sometimes it can go too far and get a non-functional individual. [1]: https://www.nature.com/articles/s42256-024-00821-x https://www.nature.com/articles/s42256-024-00821-x
        • dekhn 2y ago
          Yeah that paper does not seem intuitive to me. I'm probably just bitter because I worked so hard to reproduce the original papers results only to realize that it didn't work very well and the author's basically swept that under the rug. I could have saved a month if they had just shared their code and weights. The element example I give is a perfect example of where it seems very unlikely that generating invalid representations would be useful
          • 2y ago
    • LegionMammal978 2y ago
      As the language is usually presented, it has the syntactic requirement that all square brackets are properly paired. Of course, many interpreters (including the original one IIRC) don't fully validate this, but they will have inconsistent behavior on unpaired brackets. Here, the authors had to further specify that jumping from an unpaired bracket causes the program to halt.
    • 29athrowaway 2y ago
      I think "]" requires to be preceded by "[". Depending how to handle "<", and ">" you can have out of bounds errors. And "+" and "-" can lead to overflow/underflow. Unless you wrap or saturate values. Some programs can also lead to infinite loops. So there are "invalid" programs for these purposes. What I do is to mark the program as invalid when these problems are present. For infinite loop detection, I give the program a limited amount of iterations and if it doesn't finish when the max limit is reached the program is marked as invalid.
• jekude 2y ago
  Combinatory Chemistry [0] is a great paper that is referenced. Using Combinatory Logic feels a lot cleaner than brainfuck IMO. [0] https://arxiv.org/abs/2003.07916 https://arxiv.org/abs/2003.07916
• deleted 2y ago
  [deleted]
• 29athrowaway 2y ago
  Brainfuck is a useful language for evolutionary programming because it is Turing complete, it has few instructions, the interpreter is easy to implement, and a mutation operator is also easy to implement. There are different ways to deal with bounds checking when moving the tape: saturation, wrapping and invalidation. I often chose to invalidate a program that crosses bounds, as it usually generates a cleaner program that is more compatible with other interpreters as well. In the paper the part that's interesting is that there was no explicit fitness functions. The higher fitness emerges in the form of the replicator. https://www.youtube.com/watch?v=eOHGBuZCswA https://www.youtube.com/watch?v=eOHGBuZCswA
  • deleted 2y ago
    [deleted]
• JyrkiAlakuijala 2y ago
  Zilog Z80: The reports of my death are greatly exaggerated. I'm actually creating life nowadays.
  • muragekibicho 2y ago
    Lol I saw your tweet