[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.