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

https://arxiv.org/abs/2406.19108

by jasondavies • 2 years ago

141 17 2 years ago

arxiv.org

JyrkiAlakuijala• 2 years ago

Zilog Z80: The reports of my death are greatly exaggerated. I'm actually creating life nowadays.

muragekibicho• 2 years ago

Lol I saw your tweet

p1esk• 2 years ago

They use Brainfuck language for the experiments. Seriously.

Zondartul• 2 years ago

It's convienient because any random collection letters is a "valid" brainfuck program.

optimalsolver• 2 years ago

StupidStackLanguage also has this pleasing property:

https://esolangs.org/wiki/StupidStackLanguage

dekhn3• 2 years 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) 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.

LegionMammal978• 2 years 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.

29athrowaway3• 2 years 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• 2 years 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

29athrowaway3• 2 years 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

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

Related Stories