[mtlmtlmtlmtl]

I always felt like unlambda and other SKI calculus esque esolangs(iota comes to mind) could have some kinda strange use case in some kind of generalised genetic programming. It should be possible to create a binary notation for SKI calculus where arbitrary bitstrings will be valid, and so one could randomly mutate and recombine arbitrary programs. Though I've never delved deeper into genetic algorithms and evolutionary programming, my sense is that genetic algorithms tend to be restricted to parameterised algorithms where the "genes" determine the various parameters. Which can be great for optimisation problems.

It's one of those weird ideas I've had kicking about for years but never did anything about, and yet I keep coming back to it.

[alcover]

This must be an avenue for very exciting explorations. I'm quite ignorant about this stuff but have some questions :

  > It should be possible to create a binary notation for SKI calculus where arbitrary bitstrings will be valid

What if it's not ? How will your genetic petri dish spot and eliminate invalid programs ?

  > one could randomly mutate and recombine arbitrary programs

What if non-halting programs get generated ?

In this vein I've seen magnificent images of 1D cellular automatons that use the surrounding pattern to decide on the local rule for next gen.

[mtlmtlmtlmtl]

I assume that an invalid program would not compile/parse, and so would die and fail to reproduce. The issue is more that if the space of invalid programs is too large compared to the space of valid ones, generating valid offspring by combining two programs would be too rare and the population would die off.

Though if the space is small enough I imagine you could get past that. It's a bit of a gnarly point, hard to tell how this would turn out without trying I suppose.

As for the halting problem there's of course no clever solution there other than limiting CPU time. So I guess pick a reasonable limit that makes sense for whatever you're trying to do.