@amiloradovsky Carl Zimmer of the NYT posted a story some years back on a computer simulation of problem-solving behaviours where an "organism" (simulated) had to "evolve" a set of capabilities to solve some problem (maze traversal IIRC).
There was no complexity cost constraint (so highly-complex organisms evolved), but success required some *minimum* set of abilities which showed up in the experiment. Statsitically demonstrable if not logically provable.